Lecture Data Structures: Lesson 31

Lecture Data Structures: Lesson 31 provide students with knowledge about buildheap; the general algorithm is to place the N keys in an array and consider it to be an unordered binary tree; the following algorithm will build a heap out of N keys;...
Nội dung trích xuất từ tài liệu:
Lecture Data Structures: Lesson 31BuildHeap The general algorithm is to place the N keys in an array and consider it to be an unordered binary tree. The following algorithm will build a heap out of N keys. for( i = N/2; i > 0; i-- ) percolateDown(i); BuildHeap 1 WhyI=n/2?i = 15/2 = 7 65 2 31 3 32 4 26 5 21 6 19 7 68 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 12 13 i 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i = 15/2 = 7 65 2 31 3 32 4 26 5 21 6 19 7 12 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i=6 65 2 31 3 32 4 26 5 21 6 19 i 7 12 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i=5 65 2 31 3 32 4 26 5 21 i 6 5 7 12 8 9 24 10 15 11 14 12 16 13 19 14 70 15 68 13 i 65 31 32 26 21 5 12 13 24 15 14 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i=4 65 2 31 3 32 4 26 i 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 13 i 65 31 32 26 14 5 12 13 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i=3 65 2 31 3 32 i 4 13 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 26 i 65 31 32 13 14 5 12 26 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1i=2 65 2 31 i 3 5 4 13 5 14 6 16 7 12 8 9 24 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 31 5 13 14 16 12 26 24 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 ii=1 65 2 13 3 5 4 24 5 14 6 16 7 12 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 13 5 24 14 16 12 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1Min heap 5 2 13 3 12 4 24 5 14 6 16 7 65 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 5 13 12 24 14 16 65 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Other Heap Operations decreaseKey(p, delta): lowers the value of the key at position ‘p’ by the amount ‘delta’. Since this might violate the heap order, the heap must be reorganized with percolate up (in min heap) or down (in max heap). increaseKey(p, delta): opposite of decreaseKey. remove(p): removes the node at position p from the heap. This is done by first decreaseKey(p, ) and then performing deleteMin(). Heap code in C++template class Heap{ public: ...