COMP171Fall2005Heaps and heapsortPart 2
Heaps and heapsort COMP171 Fall 2005 Part 2
Sorting/Slide2Heap: array implementation17101420161889171410201816Is it a good idea to store arbitrary binary trees as arrays? May havemany empty spaces!
Sorting III / Slide 2 Heap: array implementation Is it a good idea to store arbitrary binary trees as arrays? May have many empty spaces!
Sortingl/Slide3Array implementationThe root node is A[1]The left child of Ali] is A[2j]The right child of Alil is A[2j + 1]The parent of Alij is A[j/2] (note: integer divide)Needto estimatethemaximumsize of theheap
Sorting III / Slide 3 Array implementation The root node is A[1]. The left child of A[j] is A[2j] The right child of A[j] is A[2j + 1] The parent of A[j] is A[j/2] (note: integer divide) Need to estimate the maximum size of the heap
SortingIl/ Slide4Heapsort(1)Build a binary heap of N elementstheminimumelement is at thetop of theheap(2)PerformN DeleteMin operationstheelementsareextractedinsortedorder(3) Record these elements in a second array and thencopythearrayback
Sorting III / Slide 4 Heapsort (1) Build a binary heap of N elements the minimum element is at the top of the heap (2) Perform N DeleteMin operations the elements are extracted in sorted order (3) Record these elements in a second array and then copy the array back
Sorting/ Slide5Heapsort - running time analysis(1)BuildabinaryheapofNelementsrepeatedly insertNelements=O(NlogN)time(thereisamoreefficientway)PerformN DeleteMin operations(2)EachDeleteMin operationtakesO(logN)=O(NlogN)(3)Recordtheseelementsinasecondarrayandthencopy the array backO(N)Total: O(N log N)Uses an extra array
Sorting III / Slide 5 Heapsort – running time analysis (1) Build a binary heap of N elements repeatedly insert N elements O(N log N) time (there is a more efficient way) (2) Perform N DeleteMin operations Each DeleteMin operation takes O(log N) O(N log N) (3) Record these elements in a second array and then copy the array back O(N) Total: O(N log N) Uses an extra array