Heap Sort

Heap Sort is variant of a selection sort.
Heap Sort is O(N log N), but it's almost always slower than either Quick Sort or Merge Sort.
It's also more confusing than Quick Sort or Merge Sort, so it's rarely used.
Heap Sort does have one interesting bit, the concept of a heap

What's a heap?
A heap (as used in heap sort) is a binary tree where each node has (at most) two child nodes.

The bottom row of the heap is always filled from left to right.
Every node forms a sub-heap -- all the values that descend from that node.
If each parent is not smaller than it's children, then the heap is called "correct".
If a parent is smaller than one of it's children, then the heap is called "incorrect".
If a sub-heap is incorrect, any heap that contains it is also incorrect.

(In this example, the incorrect heaps are colored yellow)

There are few things to take note of;

A node without children is correct.
You can remove the last element on the bottom right of a correct heap, and you will still have a correct heap.
Every parent node in a correct heap is bigger than all it's descendants (all values beneath it in the heap).
The top element is always the biggest element in a correct heap.

There are several operations that can be done on a heap.
If you want the full description, here's a link that explains more of what a heap is and some other things about heaps in general.

For Heap Sort, the only operations we need are Sift-Down and Heapify

Sift-Down;
Starting with the parent of two correct child nodes;

If the parent is not smaller than it's child nodes, then the heap is correct.

If not, then swap the parent with the biggest child node. Now the new parent node is bigger than the both child nodes.

Go to the child node you swapped with, and repeat the procedure.

Continue until either the parent is already bigger when sifted down (no swap necessary) or you reach the bottom of the heap.

For heap sort to work, we need to start with a correct heap.
To create a correct heap, we use the procedure Heapify;

Heapify
Starting with the last parent node and working backwards to the top, call sift down on each node.

Since a child-less node is correct, the last parent node is guaranteed to be atop two correct sub-nodes.
As we work backwards, each node is atop sub-nodes that have already been sifted-down, and are thus correct.
Once every node has been sifted down, the entire heap is correct.

Once we have a correct heap, we sort it by repeating the following until the heap is empty;

Move the top element of the heap to the end of the sorted list (the top element is the biggest value)
Move the last element of the heap to the top. This will result in two correct child heaps with an incorrect parent
Call Sift-Down on the top node.

A few frequently asked questions;

Is Heapify really O(N) ?
Yes, it is.
The worst case given the worst possible heap is N-1.
The quick explanation is that each row added to the heap increases N, and increases difficulty by (almost) the same amount.
Here's a link to a more complete explanation
What are those other functions you mentioned?
If you want the full description, here's a link that explains what a heap is and some other things about heaps in general.

^ UP ^ < Back < > Next >