Programming Pearls Clmn 14

Can you write a heap without a single error?

The author said we need 2 critical functions. One is siftUp, one is siftDown.

When I insert one element, I put it at the end of heap. Then shift it up until it’s proper location.

When I delete the top element, I put the last one of the heap to replace the first one. Then shift the new top down, until his proper location.

When we do heap sort. Do we need both siftUp and siftDown? No.

What we need to do is to build up the heap and delete the top element one by one, then maintain. And the building-up steps can be down using the maintain function.

https://github.com/NTU-FSM/ACMaimeng-cheat-sheet#%E5%A0%86-heap

Here is a source code for heap sort.

Here is a important note you should remember:

4. Heaps replace an O(n) process by a O(log n) process in all the programs.

That is the ultimate charm of Heap.