While trying to implement a heapsort in python I came across pseudocode that communicated that sifting up and sifting down to build the heap are different approaches to the same things. They both work well for creating a heap. Sifting down will move the element to a sorted position in the tree. Sifting up will move single leaf up to a lower level of the tree.
1 2 3 4 5 6 7 8 9 10 11 function siftUp(a, start, end) is input: start represents the limit of how far up the heap to sift. end is the node to sift up. child := end while child > start parent := floor((child - 1) / 2) if a[parent] < a[child] then (out of max-heap order) swap(a[parent], a[child]) child := parent (repeat to continue sifting up the parent now) else return
The Psuedocode from Wikipedia shows a full implementation with up sifting, and then shows the downsifting code–seeming to indicate that a call to siftdown() and siftup() are interchangeable. After a heapsort swap our heap is damaged and while sifting down will repair the heap, sifting up will not.
After the swap that puts the largest (root) item in the last (sorted) position of the array, sifting down will repair the damaged heap by placing the new root (the swapped leaf) into a correct position. Sifting down runs in O(n) while sifting up doesn’t fare as well running O(n log n), so sifting down probably preferred.
Heapsort with Downsifting
Sifting up will simply look at the last item of the heap and check to see it needs sifting! For our broken heap, this will only cause a swap if the leaf is one level deep and it won’t necessarily repair the tree. I discovered this on my own, as have others. Its an easy mistake to make, especially from sources that seem confused themselves.
Here’s some pseudocode taken from the web
1 2 3 4 5 6 7 8 9 10 11 12 13 heapSort(array) : //get max at root maxheapify(array) end = array.length() -1 while end > 0 : // put max at the end swap(0, end) end-- // put heap in max-heap order again siftDown(0, end) // or siftUp(0, end)
So, if you are determined to upsift, perhaps as an exercise, you have two options. One is to use it only to create your initial heap, and use downsifting thereafter. Or, you can upsort in a loop and essentially heapify your elements a second time.
1 2 3 4 5 6 7 8 HeapSort(items) : end = len(items) - 1 heapify_siftup(items, len(items)) while end > 0 : swap(items[end], items) heapify_siftup(items, end) end-- return items
I have both heapsorts implemented in python on Github.