HEAP

Information about HEAP

Published on August 8, 2014

Author: kavitharangaswamy

Source: authorstream.com

Content

PowerPoint Presentation: HEAP CONTENTS: CONTENTS 1. DEFINITION 2. Max tree & min tree 3. Types of HEAP 4. HEAP operations 4.1. insertion into a Max Heap 4.2. Deletion from a Max Heap 4.3. Max Heap Initialization 5. Applications of heap 5.1. sorting using heap tree 5.2. priority queue 1. DEFINITION: 1. DEFINITION A Heap is a Binary Tree Structure with the following properties: 1. The tree is Full (or) Complete Binary Tree. 2. The key value of each node is greater than or equal to the key value in each of its descendents . K all <=K all <= K 2.MAX TREE & MIN TREE: 2.MAX TREE & MIN TREE Definition . Max Tree A Max tree is a tree in which, value in each node is greater than (or) equal to those in it’s children. 7 12 10 8 6 6 5 14 9 30 25 a b c PowerPoint Presentation: Min Tree A Min tree is a tree in which, value in each node is less than (or) equal to those in it’s children. It’s not necessary for a max tree to be binary. Nodes of a max (or) min tree may have an arbitrary number of children 4 7 10 8 6 20 50 2 10 11 21 a b c PowerPoint Presentation: 3. TYPES OF HEAP Max Heap A max heap is a max tree that’s also a complete binary tree 7 12 10 8 6 6 5 14 9 30 25 a b c Fig (a) & (b) are Max heap, because it’s a complete binary tree Fig (c) is not a Max heap because, it’s not a complete binary PowerPoint Presentation: Min Heap A min heap is a min tree that’s also a complete binary tree 4 7 10 8 6 11 21 2 50 10 20 a b c Fig (a) & (b) are Min heap, because both the trees are complete binary trees Fig (c) is not a Min heap because, it’s not a complete binary 4.Heap Operations: 4.Heap Operations Two basic operations 1. Insert 2. Delete To implement the insert and delete operations, we need two basics operations 1. Reheap up - this operation will take place when inserting a new node into the tree 2. Reheap down - this operation will take place when deleting a node from the tree 1. REHEAP UP: 1. REHEAP UP DEFINITION The Reheap-Up operation repairs a “broken” heap by floating the last element up the tree until it is in its correct location in the heap. 32 21 16 12 20 42 30 13 10 15 25 (a) Original Tree: not a heap after insertion of node (25) PowerPoint Presentation: 32 21 16 25 20 42 30 13 10 15 32 25 16 21 20 42 30 13 10 15 12 12 Step-1 Step-2 4.1. insertion into a Max Heap : 4.1. insertion into a Max Heap Let us take the following figure ------ Fig.1 This is the Max Heap with five elements. When an element is added to this heap, the resulting 6 th element position is shown in the following figure: 2 15 14 10 20 2 15 14 10 20 6 th element position PowerPoint Presentation: The insertion can be completed by placing the new element into the new node and then bubbling the new element up the tree (along the path from the new node to the root) until the new element has a parent whose priority is > = of the new element. Suppose if we want to insert the element ‘1 ’, (in Fig-1), it may be inserted as the left child of the node ‘2’. Instead of inserting the element ‘1’, insert the element ‘5 ’, (in Fig-1) this element is placed as the left child. But according to the definition of Max heap, the element ‘2’ is moved down to it’s left child & 5 is bubbled up one node as follow: 2 15 14 10 1 20 PowerPoint Presentation: If we want to insert the element ’21 ’, in Fig-1, it’s inserted as a left child of ‘2’, so 21 is inserted as a ‘ROOT’ node & 20 becomes right child of the element 21 and the element ‘2’ become left child of ’20’. 2 15 14 10 5 20 2 15 14 10 21 20 5 15 14 10 2 20 20 15 14 10 2 21 Algorithm for heap insertion: Algorithm for heap insertion 32 56 45 8 23 78 67 19 78 56 32 45 8 23 19 67 Heap To be inserted/heapified Before insertion (or) Before reheap – up PowerPoint Presentation: 32 56 67 8 23 78 45 19 32 67 56 8 23 78 45 19 Step-1 Step-2 PowerPoint Presentation: Step-3 : Now the node 67 was placed correctly in its position. 32 67 56 8 23 78 45 19 78 67 32 56 8 23 19 45 Aftere insertion (or) After reheap – up PowerPoint Presentation: algorithm insertHeap ( ref heap < array of datatype> ref last <index>, insert data into heap ) Precondition : heap is a valid heap structure Postcondition : data have been inserted into heap Return : True if successful ; False if array full; 1. if (heap full) 2. end if 3. last = last + 1 4. heap [last] = data 5. reheapup (heap, last) 6. return true End inserheap 4.2. Deletion from a Max Heap: 4.2. Deletion from a Max Heap 2. REHEAP DOWN Definition: ReheapDown repairs a “broken” heap by pushing the root down the tree until it is in its correct position in the heap. When deleting a node from a heap, the most common and meaningful logic is to delete the root. The heap is thus left without a root. To reestablish the heap, move the data in the last heap node to the root and reheapdown. When an element is to be removed from a Max heap, it’s taken from the root of the heap. Suppose if we want to delete the element ’21’, the resulting tree will be as follow : 20 15 14 10 2 21 PowerPoint Presentation: After deleting the root node ‘21’. The leaf node ‘2’ is placed in the root and reheapdown has to take place 20 15 14 10 2 2 15 14 10 20 PowerPoint Presentation: Deletion of node 20 will give following tree: 2 15 14 10 2 10 14 15 2 14 10 15 2 15 14 10 20 Algorithm for heap deletion: Algorithm for heap deletion 32 67 56 8 23 78 45 19 78 67 32 56 8 23 19 45 Heap To be deleted Before deletion (or) Reheap down To be deleted PowerPoint Presentation: 32 67 56 8 23 45 19 32 45 56 8 23 19 67 Step-1 Step-2 PowerPoint Presentation: 32 56 45 8 23 67 19 67 56 32 45 8 23 19 After deletion (or) After Reheap down Step-3 PowerPoint Presentation: algorithm deletetHeap ( ref heap < array of datatype>, ref last <index>, delete root of heap & passes data back to caller) Precondition : heap is a valid heap structure, last is index to last node in heap, Postcondition : root has been deleted from heap root data placed in dataout. Return : True if successful ; False if array full; 1. if (heap full) 1.1. return false 2. end if 3. dataout = heap [0 ] 4. heap [0] = heap [last] 5. reheapdown (heap, 0, last) 6. return true End deleteHeap 4.3. Max Heap Initialization : 4.3. Max Heap Initialization Let us consider an array a[ ] with n-elements. Assume n=10 and the priority of the elements in a[10] is as follow: a[20, 12, 35, 15, 10, 80, 30, 17, 2, 1] Suppose this array elements are arranged in a complete binary tree, as shown in the following fig. 35 12 15 10 80 20 30 17 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] PowerPoint Presentation: This complete binary tree is not a ‘Max Heap’, To heapify (make into a max heap) the above complete binary tree, use i = n/2 formula 1. Definition of Max Heap Max heap is a max tree that is also a complete binary tree 2. From the above figure, the positions [4] and [8] are not satisfying the definition of Max heap. So in this array position the heapify is going to take place. The position going to be heapified is [8], applying this in i = n/2 ; i = 8/2 = 4 2 17 15 2 15 17 [8] [4] [9] [8] [4] [9] PowerPoint Presentation: The heapified tree is as follow: 35 12 17 10 80 20 30 15 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified- [Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: Now take this is also not in Max Heap definition. The array size to be heapified is [6]. (i.e) i=n/2; 6/2=3 so the element in array position [6] is changed to array position [3] as given below: 30 80 35 [6] [3] [7] 30 35 80 [8] [4] [9] i PowerPoint Presentation: The heapified tree is as follow: 80 12 17 10 35 20 30 15 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified- [Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: Now also, the above fig. is not a Max heap, because this is also not in Max Heap definition. The array size to be heapified is [4]. (i.e) i=n/2; 4/2=2 so the element in array position [4] is changed to array position [2] as given below: 10 17 12 [4] [2] [5] 10 12 17 [4] [2] [5] i PowerPoint Presentation: The heapified tree is as follow: 80 17 12 10 35 20 30 15 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified- [Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: Now take this is also not in Max Heap definition. The array size to be heapified is [8]. (i.e) i=n/2; 8/2=4 so the element in array position [8] is changed to array position [4] as given below: 2 15 12 [8] [4] [9] 2 12 15 [8] [4] [9] i PowerPoint Presentation: The heapified tree is as follow: 80 17 15 10 35 20 30 12 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified-[ Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: Still also the array position[3] to be heapified this is also not in Max Heap definition. The array size to be heapified is [3]. (i.e) i=n/2; 3/2=1 so the element in array position [3] is changed to array position [1] as given below: 80 17 20 [2] [1] [3] 20 17 80 [2] [1] [3] i PowerPoint Presentation: The heapified tree is as follow: 20 17 12 10 35 80 30 15 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified- [Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: Still also the array position[6] to be heapified this is also not in Max Heap definition. The array size to be heapified is [6]. (i.e) i=n/2; 6/2=3 so the element in array position [6] is changed to array position [3] as given below: 30 35 20 [6] [3] [7] 30 20 35 [6] [3] [7] i PowerPoint Presentation: The heapified tree is as follow: 35 17 12 10 20 80 30 15 1 2 [1] [2] [3] [4] [5] [8] [9] [10] [6] [7] Heapified- [Now this subtree is satisfying “Max Heap” definition ] PowerPoint Presentation: According to Max Heap – definition: (i) the Root node 80 – is greater than it’s children node – 17, 35 (ii) the Root node 17 – is greater than it’s children node – 15, 10 (iii) the Root node 35 – is greater than it’s children node – 20, 30 (iv) the Root node 15 – is greater than it’s children node – 12, 2 5.Applications of heap tree: 5.Applications of heap tree There are two main applications of heap trees 1. Sorting using Heap Tree - the sorting method which is based on heap tree is called :Heap Sort”. And this is the efficient sorting method. 2. Priority Queue implementation using Heap Tree - Priority Queue ca be implemented using circular array, Linked List etc., Another simplified implementation is possible using heap tree, the heap, however, can be represented using an array. This implementation is therefore free from the complexities of circular array and Linked List but getting the advantages of simplification of array. 1. Sorting using Heap Tree / Heap Sorting: 1. Sorting using Heap Tree / Heap Sorting Any kind of data can be sorted either in ascending order or in descending order using heap tree. This actually comprises of the following steps: Phase 1: Build a heap tree with the given set of data to sort the data in ascending /descending order, we have to built Max heap / Min heap in step-1. Phase 2: (a) Delete the root node from the heap. (b) Place the last leaf node in the root position. (c) Rebuild the heap. (d) Place the deleted node in the output. Phase 3: Continue Step-2 until the heap tree is empty. PowerPoint Presentation: EXAMPLE Sort the following set of data in Ascending Order 33, 14, 65, 2, 76, 69, 59, 85, 47, 99, 98 Phase 1: Build a heap tree with the given set of data Step 1 Step 2: Insert the element ‘14’ 33 33 14 PowerPoint Presentation: Step 3: Insert the element ‘65’ Step 4: Insert the element ‘2’ 33 14 65 65 14 33 65 14 33 2 PowerPoint Presentation: 65 14 33 2 76 65 76 33 2 14 76 65 33 2 14 Step 5: Insert the element ’76’ PowerPoint Presentation: Step 6: Insert the element ‘69’ Step 7: Insert the element ‘59’ 33 65 2 14 69 76 69 65 2 14 33 76 69 65 2 14 33 76 59 PowerPoint Presentation: Step 8: Insert the element ‘85’ 69 65 2 14 33 76 59 69 65 85 14 33 76 59 85 2 PowerPoint Presentation: 69 85 65 14 33 76 59 2 69 76 65 14 33 85 59 2 PowerPoint Presentation: Step 9: Insert the element ’47’ 69 76 65 14 33 85 59 2 47 PowerPoint Presentation: 69 76 65 14 33 85 59 2 47 99 69 76 65 99 33 85 59 2 47 14 Step 10: Insert the element ’99’ PowerPoint Presentation: 69 99 65 76 33 85 59 2 47 14 69 85 65 76 33 99 59 2 47 14 PowerPoint Presentation: Step 11: Insert the element ’98’ 69 85 65 76 33 99 59 2 47 14 69 85 65 98 33 99 59 2 47 14 98 76 PowerPoint Presentation: 69 98 65 85 33 99 59 2 47 14 76 The construction of Heap tree for the given set of data was over. Now move to Phase 2, to carry out the Deletion and Rebuilding of data in the Heap tree PowerPoint Presentation: Phase 2: (a) Delete the root node from the heap. (b) Place the last leaf node in the root position. (c) Rebuild the heap. (d) Place the deleted node in the output. Step 1: Delete the root node ‘99’ and place it in the output, and place the last leaf node ‘76’ in the root position 69 98 65 85 33 99 59 2 47 14 76 99 98 69 65 85 33 59 2 47 14 76 Leaf Node PowerPoint Presentation: 69 98 65 85 33 76 59 2 47 14 76 98 69 65 85 33 59 2 47 14 99 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: OUTPUT: PowerPoint Presentation: 69 98 65 85 33 76 59 2 47 14 69 76 65 85 33 98 59 2 47 14 PowerPoint Presentation: 69 85 65 76 33 98 59 2 47 14 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 98 85 69 65 76 33 59 2 47 14 99 PowerPoint Presentation: 69 85 65 76 33 98 59 2 47 14 98 85 69 65 76 33 59 2 47 14 99 Step 2: Delete the root node ‘98’ and place it in the output , and place the last leaf node ‘14’ in the root position. Leaf Node PowerPoint Presentation: 69 85 65 76 33 14 59 2 47 14 85 69 65 76 33 59 2 47 98 99 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: OUTPUT: PowerPoint Presentation: 69 85 65 76 33 14 59 2 47 69 14 65 76 33 85 59 2 47 PowerPoint Presentation: 69 76 65 14 33 85 59 2 47 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 85 76 69 65 14 33 59 2 47 98 99 OUTPUT: PowerPoint Presentation: 69 76 65 14 33 85 59 2 47 Step 3: Delete the root node ‘85’ and place it in the output and place the last leaf node ‘47’ in the root position. 85 76 69 65 14 33 59 2 47 98 99 Leaf Node OUTPUT: PowerPoint Presentation: 69 76 65 14 33 47 59 2 47 76 69 65 14 33 59 2 85 98 99 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: OUTPUT: PowerPoint Presentation: 69 76 65 14 33 47 59 2 69 47 65 14 33 76 59 2 PowerPoint Presentation: 69 65 47 14 33 76 59 2 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 76 65 69 47 14 33 59 2 85 98 99 OUTPUT: PowerPoint Presentation: 69 65 47 14 33 76 59 2 Step 4: Delete the root node ‘76’ and place it in the output, and place the last leaf node ‘2’ in the root position. 76 65 69 47 14 33 59 2 85 98 99 Leaf Node OUTPUT: PowerPoint Presentation: 69 65 47 14 33 2 59 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 2 65 69 47 14 33 59 76 85 98 99 OUTPUT: PowerPoint Presentation: 69 65 47 14 33 2 59 2 65 47 14 33 69 59 PowerPoint Presentation: 59 65 47 14 33 69 2 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 69 65 59 47 14 33 2 76 85 98 99 OUTPUT: PowerPoint Presentation: 59 65 47 14 33 69 2 Step 5: Delete the root node ‘69’ and place it in the output, and place the last leaf node ‘2’ in the root position. Leaf Node 69 65 59 47 14 33 2 76 85 98 99 OUTPUT: PowerPoint Presentation: 59 65 47 14 33 2 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 2 65 59 47 14 33 69 76 85 98 99 OUTPUT: PowerPoint Presentation: 59 65 47 14 33 2 59 2 47 14 33 65 PowerPoint Presentation: 59 47 2 14 33 65 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 65 47 59 2 14 33 69 76 85 98 99 OUTPUT: PowerPoint Presentation: 59 47 2 14 33 65 65 47 59 2 14 33 69 76 85 98 99 OUTPUT: Step 6: Delete the root node ‘65 and place it in the output, and place the last leaf node ‘33’ in the root position. Leaf Node PowerPoint Presentation: After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 59 47 2 14 33 33 47 59 2 14 65 69 76 85 98 99 OUTPUT: PowerPoint Presentation: 59 47 2 14 33 33 47 2 14 59 PowerPoint Presentation: 33 47 2 14 59 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. 59 47 33 2 14 65 69 76 85 98 99 OUTPUT: PowerPoint Presentation: 33 47 2 14 59 59 47 33 2 14 65 69 76 85 98 99 OUTPUT: Step 7: Delete the root node ‘59 and place it in the output, and place the last leaf node ‘14’ in the root position. Leaf Node PowerPoint Presentation: 33 47 2 14 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 14 47 33 2 59 65 69 76 85 98 99 OUTPUT: PowerPoint Presentation: 33 47 2 14 33 14 2 47 PowerPoint Presentation: 33 14 2 47 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. OUTPUT: 47 14 33 2 59 65 69 76 85 98 99 PowerPoint Presentation: 33 14 2 47 OUTPUT: Step 8: Delete the root node ‘47‘ and place it in the output, and place the last leaf node ‘2’ in the root position. 47 14 33 2 59 65 69 76 85 98 99 Leaf Node PowerPoint Presentation: After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 33 14 2 OUTPUT: 2 14 33 47 59 65 69 76 85 98 99 PowerPoint Presentation: 33 14 2 2 14 33 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. OUTPUT: 33 14 2 47 59 65 69 76 85 98 99 PowerPoint Presentation: Step 9: Delete the root node ‘33‘ and place it in the output, and place the last leaf node ‘2’ in the root position. Leaf Node 2 14 33 OUTPUT: 33 14 2 47 59 65 69 76 85 98 99 PowerPoint Presentation: 14 2 After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: OUTPUT: 2 14 33 47 59 65 69 76 85 98 99 PowerPoint Presentation: OUTPUT: 14 2 33 47 59 65 69 76 85 98 99 14 2 2 14 After Reheapdown the leaf node was placed in a correct place. And the tree has become perfect Heap Tree. PowerPoint Presentation: Step10: Delete the root node ‘14‘ and place it in the output, and place the last leaf node ‘2’ in the root position. 2 14 OUTPUT: 14 2 33 47 59 65 69 76 85 98 99 Leaf Node PowerPoint Presentation: After swapping the root node and the last node, the next step is to rebuild the heap tree. Because after swapping the resultant tree is not a Heap tree, so rebuild the heap tree using “REHEAPDOWN” process as follow: 2 OUTPUT: 2 14 33 47 59 65 69 76 85 98 99 PowerPoint Presentation: Step11: The remaining node is ‘2’ place it in the output. OUTPUT: 2 14 33 47 59 65 69 76 85 98 99 2 Leaf Node PowerPoint Presentation: OUTPUT: 2 14 33 47 59 65 69 76 85 98 99 Phase 3: Continue Step-2 until the heap tree is empty. After placing the node ‘2’ in the output, the Heap tree has become empty. The sorted data is placed in the output as follow: PowerPoint Presentation: 2. Priority Queue implementation using Heap Tree 1. Elements associated with their priority values are to be stored in the form of heap tree, which can be formed based on their priority values. 2. The top priority element that has to be processed first is at the root . So, it can be deleted and heap can be rebuilt to get the next element to be processed. 3. Example: Consider the following processes with their priorities: Process P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 Priority 5 4 3 4 5 5 3 2 1 5 PowerPoint Presentation: 1 st Top Priority element and process : 5 (p1,p5,p6,p10) 2 nd Top Priority element and process : 4 (p2,p4) 3 rd Top Priority element and process : 3 (p3,p7) 4 th Top Priority element and process : 2 (p8) 5 th Top Priority element and process : 1 (p9) Construction of Heap Tree: Step 1: P 3 (3 ) P 2 (4) P 4 (4) P 5 (5) P 6 (5) P 1 (5) P 7 (3) P 8 (2) P 9 (1) P 10 (5) PowerPoint Presentation: P 3 (3 ) P 2 (4) P 4 (4) P 5 (5) P 6 (5) P 1 (5) P 7 (3) P 8 (2) P 9 (1) P 10 (5) P 6 (5) P 5 (5) P 4 (4) P 2 (4) P 3 (3) P 1 (5) P 7 (3) P 8 (2) P 9 (1) P 10 (5) Step 2: PowerPoint Presentation: P 6 (5 ) P 5 (5) P 4 (4) P 10 (5) P 3 (3) P 1 (5) P 7 (3) P 8 (2) P 9 (1) P 2 (4) Step 3: THOUGHT: THOUGHT Dream visit us, when we are asleep But God is truly wise – he wakes us up Every Day and Give us each chance To make our Dream come true – So, keep trying for your Dream

Related presentations