Data Structures and Agorithm: DS 18 Heap.pptx

Data Structures and Agorithm: DS 18 Heap.pptx

1. International Islamic University H-10, Islamabad, Pakistan Data Structure Lecture No. 18 Heap Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti Video Lecture

2. A heap is a complete binary tree that conforms to the heap order. The heap order property: In a (min) heap, for every node X, the key in the parent is smaller than (or equal to) the key in X. Or , the parent node has key smaller than or equal to both of its children nodes Heap 21 16 13 68 65 26 19 24 32 31 This is a min heap 27 19 13 68 65 26 16 27 32 31 Not a heap: heap property violated  

3. Heap can be represented as an array and the root is stored at index no. 1 At any position (index) i Left child is at position 2i Right child is at position 2i + 1 Parent is at position i /2 Heap: Array Implementation 21 16 13 68 65 26 19 24 31 32 13 21 16 24 31 19 68 65 26 32 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10

4. Place new data in x ; Find the empty position i . If x is less than data at Position i /2 Move data at i /2 to Position i , … repeat step 3 until the root is reached Heap: Inserting into a heap 21 16 13 68 65 26 19 24 31 13 21 16 24 31 19 68 65 26 32 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 32

5. Insert(14 ) Find the empty position i =11 . Heap: Insert 14 into a heap 21 16 13 68 65 26 19 24 31 13 21 16 24 31 19 68 65 26 32 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 32

6. If 14 is less than data at Position i /2 = 11/2 = 5 Move data at i /2 to Position i Move 31 at 5 to Position 11 Heap: Insert 14 into a heap 21 16 13 68 65 26 19 24 31 13 21 16 24 31 19 68 65 26 32 31 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 31 11 32

7. Now i = i /2 = 11/2 = 5 If 14 is less than data at Position i /2 = 5 /2 = 2 Move data at i /2 to Position i Move 14 at 2 to Position 5 Heap: Insert 14 into a heap 21 16 13 68 65 26 19 24 21 13 21 16 24 21 19 68 65 26 32 31 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 31 11 32

8. Now i = i /2 = 5 /2 = 2 If 14 is less than data at Position i /2 = 2 /2 = 1 If 14 is less than 13 Which is false condition So place 14 at index 2 . Heap: Insert 14 into a heap 14 16 13 68 65 26 19 24 21 13 14 16 24 21 19 68 65 26 32 31 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 31 11 32

9. Insert(15) Find the empty position i =12 . Heap: Insert 15 into a heap 68 13 14 16 24 21 19 68 65 26 32 31 1 2 3 4 5 6 7 8 9 10 11 12 13 1 3 7 14 65 26 24 21 2 4 5 6 8 9 10 31 11 32 16 19 19 12 13

10. If 15 is less than data at Position i /2 = 12 /2 = 6 Move data at i /2 to Position i Move 19 at 6 to Position 12 Heap: Insert 15 into a heap 68 13 14 16 24 21 19 68 65 26 32 31 19 1 2 3 4 5 6 7 8 9 10 11 12 13 1 3 7 14 65 26 24 21 2 4 5 6 8 9 10 31 11 32 16 19 19 12 13

11. Now i = i /2 = 12/2 = 6 If 15 is less than data at Position i /2 = 6 /2 = 3 Move data at i /2 to Position i Move 16 at 3 to Position 6 Heap: Insert 15 into a heap 68 13 14 16 24 21 16 68 65 26 32 31 19 1 2 3 4 5 6 7 8 9 10 11 12 13 1 3 7 14 65 26 24 21 2 4 5 6 8 9 10 31 11 32 16 16 19 12 13

12. Now i = i /2 = 6 /2 = 3 If 15 is less than data at Position i /2 = 3 /2 = 1 If 15 is less than 13 Which is false condition So place 15 at index 3 . Heap: Insert 15 into a heap 68 13 14 15 24 21 16 68 65 26 32 31 19 1 2 3 4 5 6 7 8 9 10 11 12 13 1 3 7 14 65 26 24 21 2 4 5 6 8 9 10 31 11 32 15 16 19 12 13

13. Finding the minimum is easy; it is at the top of the heap. Deleting it (or removing it) causes a hole which needs to be filled . Min_Node = root Move the last node as the root If the root is greater than its smallest child. Interchange the root with the smallest child Continue down the tree Heap: Get_Min () 68 1 3 7 14 65 26 24 21 2 4 5 6 8 9 10 31 11 32 15 16 19 12 13

14. Get_Min () Min_Node = 13 Move the last node ( 19 ) as the root If the root( 19 ) is greater than its smallest child( 14 ). True Interchange the root with the smallest child Continue down the tree Heap: Calling Get_Min () first time 68 1 3 7 65 26 24 21 2 4 5 6 8 9 10 31 11 32 15 16 12 13 14 19

15. Get_Min () Now root is node ( 19 ) If the root( 19 ) is greater than its smallest child( 21 ). False Stop Return Min_Node = 13 Heap: Calling Get_Min () first time 68 1 3 7 65 26 24 21 2 4 5 6 8 9 10 31 11 32 15 16 14 19

16. Get_Min () Min_Node = 14 Move the last node ( 31 ) as the root If the root( 31 ) is greater than its smallest child( 15 ). True Interchange the root with the smallest child Continue down the tree Heap: Calling Get_Min () second time 68 1 3 7 65 26 24 21 2 4 5 6 8 9 10 32 15 16 11 14 19 31

17. Get_Min () Now root is node ( 31 ) If the root( 31 ) is greater than its smallest child( 16 ). True Interchange the root with the smallest child Continue down the tree Heap: Calling Get_Min () second time 68 1 3 7 65 26 24 21 2 4 5 6 8 9 10 32 31 16 15 19

18. Get_Min () Now root is node ( 31 ) Now the the root( 31 ) does not have child( ) Stop Return Min_Node = 14 Heap: Calling Get_Min () second time 68 1 3 7 65 26 24 21 2 4 5 6 8 9 10 32 16 31 15 19

19. # include < iostream > using namespace std ; class Minimum_Heap { int *Array; // pointer to array of elements in heap int Capacity; // maximum possible size of min heap int Heap_Size ; // Current number of elements in min heap public : Minimum_Heap ( int Capacity); // Constructor bool Is_Full ( ) { return Heap_Size == Capacity ; } bool Is_Empty ( ) { return Heap_Size == 0 ; } int Get_Size ( ) { return Heap_Size ; } int Parent_At ( int k) { return Array[k/2 ]; } // get the parent of node at index k int Parent ( int k) { return k/2; } // get index of parent of node at index k int Left ( int k) { return Array[2*k ]; } // get index of left child of node at index k int Right ( int k) { return Array[2*k + 1 ]; } // get index of right child of node void Insert ( int k); // Inserts a new key 'k' int Get_Min ( ); void Percolate_Down ( int hole); void Show (); }; 19 Example 1: Implementation of Heap 1

20. Minimum_Heap :: Minimum_Heap ( int cap) { Heap_Size = 0; Capacity = cap; Array = new int [cap + 1]; } void Minimum_Heap ::Insert( int x) { if ( Is_Full ()) { cout << "insert - Heap is full.\n" ; return ; } int Position = ++ Heap_Size ; // Find the empty position Array[Position ] = x ; // insert key; // move hole to its proper position for ( ; Position > 1 && x < Parent_At (Position) ; Position = Position / 2 ) Array [ Position ] = Parent_At (Position); Array[Position ] = x; } 20 Example 1: Implementation of Heap 2

21. void Minimum_Heap :: Percolate_Down ( int root_index ) { int child_index ; int root = Array[ root_index ]; for ( ; root_index * 2 <= Heap_Size ; root_index = child_index ) { child_index = root_index * 2; if ( child_index != Heap_Size && Array[ child_index ] > Array[ child_index + 1 ] ) child_index ++; // right child is smaller if ( Array[ child_index ] < root ) swap(Array [ root_index ] , Array[ child_index ]); else break ; } } void Minimum_Heap :: Show(){ for ( int i = 1 ; i <= Heap_Size; i++) { cout << Array[ i ] << " " ; } cout << endl ; } 21 Example 1: Implementation of Heap 3

22. int Minimum_Heap :: Get_Min ( ){ int min; if ( Is_Empty ( ) ) { cout << "heap is empty." << endl ; return 0; } min = Array[ 1 ]; Array [ 1 ] = Array [ Heap_Size -- ]; Percolate_Down ( 1 ); return min; } void swap( int *x, int *y) { int temp = *x; * x = *y; * y = temp; } 22 Example 1: Implementation of Heap 4

23. int main() { Minimum_Heap h(12); h.Insert (21 ); cout << "heap = " ; h.Show (); h.Insert (13 ); cout << "heap = " ; h.Show (); h.Insert (16 ); cout << "heap = " ; h.Show (); h.Insert (24 ); cout << "heap = " ; h.Show (); h.Insert (31 ); cout << "heap = " ; h.Show (); h.Insert (19 ); cout << "heap = " ; h.Show (); h.Insert (68 ); cout << "heap = " ; h.Show (); h.Insert (65 ); cout << "heap = " ; h.Show (); h.Insert (26 ); cout << "heap = " ; h.Show (); h.Insert (32 ); cout << "heap = " ; h.Show (); h.Insert (14 ); cout << "heap = " ; h.Show (); h.Insert (15 ); cout << "heap = " ; h.Show (); cout << "Min = " << h.Get_Min () << endl ; cout << "heap = " ; h.Show (); cout << "Min = " << h.Get_Min () << endl ; cout << "heap = " ; h.Show (); system ( "PAUSE " ); return 0; } 23 Example 1: Implementation of Heap 5