Lecture Data Structures: Lesson 30 provide students with knowledge about inserting into a Heap; 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; . | Data Structures Lecture 30 Sohail Aslam 1 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 12 15 65 13 14 16 24 21 19 68 65 26 32 31 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 15 7 68 8 9 26 10 32 11 31 12 19 65 13 14 16 24 21 15 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 4 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 DeleteMin 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. 1 13 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 65 6 DeleteMin deleteMin 1 2 14 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 7 DeleteMin deleteMin 1 14 2 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 8 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 8 9 26 10 32 11 31 65 9 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 11 65 10 DeleteMin deleteMin heap size is reduced by 1. 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 65 11 BuildHeap Suppose we are given as input N keys or items and we want to build a heap of the keys. Obviously this can be done with N successive inserts. Each call to insert will either take unit time leaf node or log2N if new key percolates all the way up to the root . 12 BuildHeap The worst time for building a heap of N keys could be Nlog2N. It turns out that we can build a heap in linear time. 13 BuildHeap Suppose we have a method percolateDown p which moves down the key in node p downwards. This is what was happening in deleteMin. 14 BuildHeap Initial data N 15 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7
