Binary Heaps PDF

HEAPS BINARY HEAP A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Invented by J.J Williams in 1964 ...

HEAPS BINARY HEAP A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Invented by J.J Williams in 1964  A HEAP IS EITHER A: "MAX HEAP" OR A "MIN HEAP". Max heap the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. Min heap the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node MIN HEAP EXAMPLE MIN HEAP EXAMPLE In a min heap the first element is the smallest Every parent is less than its children MAX HEAP EXAMPLE MAX HEAP EXAMPLE In a max heap the first element is the largest Every parent is greater than its children BINARY TREE In order to make our heap work efficiently, we will take advantage of the logarithmic nature of the binary tree to represent our heap. In order to guarantee logarithmic performance, we must keep our tree balanced. BINARY TREE A balanced binary tree has roughly the same number of nodes in the left and right subtrees of the root. In our heap implementation we keep the tree balanced by creating a complete binary tree. A complete binary tree is a tree in which each level has all of its nodes. THE HEAP ORDER PROPERTY The method that we will use to store items in a heap relies on maintaining the heap order property. The heap order property is as follows: In a heap, for every node x with parent p, the key in p is smaller than or equal to the key in x OFTEN THE ARE IMPLEMENTED AS ARRAYS As you know any tree can be stored as an array A heap can be stored as a complete binary tree This is very compact: There are few empty cells No pointers are required 0 1 2 3 4 5 6 7 8 9 22 16 18 8 6 15 11 4 3 OFTEN THE ARE IMPLEMENTED AS ARRAYS This is a complete binary tree that has the heap order property. You can see we can store this in an array 0 1 2 3 4 5 6 7 8 9 22 16 18 8 6 15 11 4 3 COMPLETE BINARY TREE A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. THIS IS AN IMPLICIT DATA STRUCTURE An implicit data structure stores very little information other than the main or required data. These storage schemes retain no pointers, represent a file of n k-key records as an n by k array. In implicit data structures, the only structural information is to allow the array to grow and shrink. It is called "implicit" because the order of the elements carries meaning. 0 1 2 3 4 5 6 7 8 9 Another term used interchangeably is space 22 16 18 8 6 15 11 4 3 efficient. OFTEN THE ARE IMPLEMENTED AS ARRAYS Details depend on the root position, which in turn may depend on constraints of a programming language used for implementation, or programmer preference. Specifically, sometimes the root is placed at index 1, sacrificing space in order to simplify arithmetic. 0 1 2 3 4 5 6 7 8 9 22 16 18 8 6 15 11 4 3 OFTEN THE ARE IMPLEMENTED AS ARRAYS Let n be the number of elements in the heap and i be an arbitrary valid index of the array storing the heap. If the tree root is at index 1, with valid indices 1 through n, then each element a at index i has Children at indices 2i and 2i + 1 Parent (i ∕ 2). 0 1 2 3 4 5 6 7 8 9 22 16 18 8 6 15 11 4 3 USES Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree They are also commonly used to create very efficient Queues COMMON OPERATIONS find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap (a.k.a. peek) insert: adding a new key to the heap (a.k.a., push) extract-min [or extract-max]: returns the node of minimum value from a min heap [or maximum value from a max heap] after removing it from the heap (a.k.a., pop) delete-max or delete-min: removing the root node of a max- or min-heap, respectively replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed- size heaps. CREATION create-heap: create an empty heap heapify: create a heap out of given array of elements merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps. meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps. COMMON INTERNAL FUNCTIONS increase-key or decrease-key: updating a key within a max- or min-heap, respectively delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap) shift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve. shift-down: move a node down in the tree, similar to shift-up; used to restore heap condition after deletion or replacement. IMPLEMENTATION Heaps are usually implemented in an array (fixed size or dynamic array), and do not require pointers between elements. After an element is inserted into or deleted from a heap, the heap property may be violated and the heap must be balanced by internal operations. COMPLETE BINARY TREE A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. FULL BINARY Full and almost full binary heaps may be represented in a very space-efficient way (as an implicit data structure) using an array alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n + 1 in a one-based array, or 2n + 1 and 2n + 2 in a zero-based array. COMPLETE BINARY This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by shift-up or shift-down operations (swapping elements which are out of order). As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place. INSERTION Different types of heaps implement the operations in different ways, but notably, insertion is often done by adding the new element at the end of the heap in the first available free space. 0 1 2 3 4 5 6 7 8 9 10 22 16 18 8 6 15 11 4 3 INSERTION This will generally violate the heap property, and so the elements are then shifted up until the heap property has been reestablished. 15 0 1 2 3 4 5 6 7 8 9 10 22 16 18 8 6 15 11 4 3 15 DELETING The max or min item is what is removed most often. Thus replacing is done by deleting the root and putting the new element in the root and shifting down, avoiding a shifting up step compared to pop (shift down of last element) followed by push (shift up of new element). 0 1 2 3 4 5 6 7 8 9 10 22 16 18 8 6 15 11 4 3 INSERT To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, heapify-up, or cascade- up), by following this algorithm: 1. Add the element to the bottom level of the heap. 2. Compare the added element with its parent; if they are in the correct order, stop. 3. If not, swap the element with its parent and return to the previous step. INSERT 1. Add the element to the bottom What do we need to keep track of to level of the heap. do this efficiently? 2. Compare the added element with its parent; if they are in the correct order, stop. 3. If not, swap the element with its parent and return to the previous step. INSERT 1. Add the element to the bottom What do we need to keep track of to level of the heap. do this efficiently? 2. Compare the added element with It would be nice to have the location its parent; if they are in the correct of the next open space in the tree order, stop. How could we do this? 3. If not, swap the element with its parent and return to the previous step. INSERT What do we need to keep track of to do this efficiently? It would be nice to have the location of the next open space in the tree How could we do this? What spot is this in the array? INSERT What do we need to keep track of to do this efficiently? It would be nice to have the location of the next open space in the tree How could we do this? What spot is this in the array? INSERT With the count we can easily add new items to the array and then bubble them up as needed What spot is this in the array? 10  As an example of binary heap insertion, say we have a max-heap We want to add the number 17 to the heap. We first place the 17 in the position marked by the X. However, the heap property is violated since 17 >6, so we need to swap the 17 and the 6.  As an example of binary heap insertion, say we have a max-heap The heap property is still violated since 17 > 16 We need to swap the 17 and the 16 THE INSERT IS COMPLETE SINCE 17 < 22 – THE HEAP PROPERTY IS SATISFIED RECALL THE FULL BINARY TREE binary tree in which every level, except possibly the last is completely filled all nodes are as far left as possible. Left as far as possible When using an array: This property means the array items will be in order This makes are life a lot easier WHAT IS THE COMPLEXITY OF THE INSERT? Insert thinking here? WHAT IS THE COMPLEXITY OF THE INSERT? Insert thinking here? log2(n) EXTRACT The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble- down, percolate-down, sift-down, trickle down, heapify-down, cascade- down, and extract-min/max). 1 Replace the root of the heap with the last element on the last level. 2 Compare the new root with its children; if they are in the correct order, stop. 3 If not, swap the element with one of its children and return to the previous step. a) Swap with its smaller child in a min-heap and its larger child in a max-heap. CONSIDER THIS MAX-HEAP WE REMOVE THE 22 AND REPLACE IT WITH THE 2. NOW THE HEAP PROPERTY IS VIOLATED Since 12 and 8 are greater than 2. Choose to swap with 12 since it is the largest (between 8 and 12) In this case, swapping the two elements, 2 and 12, is enough to restore the heap property and we need not swap elements further. THE EXTRACT IS NOW COMPLETE The heap property is now satisfied. WHAT IS THE COMPLEXITY OF THE EXTRACT? Insert thinking here? WHAT IS THE COMPLEXITY OF THE EXTRACT? Insert thinking here? log2(n) BINARY HEAP WORKSHEET Let's try it out