Right, so basically you take a heap and pull out the first node in the heap – as the first node is guaranteed to be the largest / smallest depending on the direction of sort. The tricky thing is re-balancing / creating the heap in the first place.
Two steps were required for me to understand the heap process – first of all thinking of this as a tree, getting my head around it, then turning that tree into an array so it could be useful.
The second part of that is to essentially traverse the tree breadth first, left to right adding each element into the array. So the following tree:
73
7 12
2 4 9 10
1
Would be {73,7,12,2,4,9,10,1}
The first part requires two steps:
- Make sure each node has two children (Unless you don’t have enough nodes to do that as in the tree above.
- Make sure each node is bigger (Or smaller if sorting min first) than its children.
So to heapify a list of numbers you add each one to the heap, then following those two steps in order.
To create my heap above I will add 10 first – it’s the only node so nothing to do.
Add 12 as it’s child on the left:
10
12
This satisfies 1, but not 2 so I will swap them round:
12
10
Add 7 – nothing to do
12
10 7
Add 73
12
10 7
73
10 < 73 so need to swap those:
12
73 7
10
12 < 73 so need to swap those:
73
12 7
10
Add 2 – nothing to do
73
12 7
10 2
Add 4 – nothing to do
73
12 7
10 2 4
Add 9
73
12 7
10 2 4 9
7 < 9 – swap
73
12 9
10 2 4 7
Add 1 – nothing to do
73
12 9
10 2 4 7
1
We have our heap 😀
Now you just remove each element from the top, swapping in the last element to the top of the tree each time, then re-balancing the tree:
Take 73 off – putting 1 in its place
1
12 9
10 2 4 7
1 < 12 – so swap them
12
1 9
10 2 4 7
1 < 10 – so swap them
12
10 9
1 2 4 7
Take 12 off – replace with 7
7
10 9
1 2 4
7 < 10 – swap them
10
7 9
1 2 4
Take 10 off – replace with 4
4
7 9
1 2
4 < 7 – swap
7
4 9
1 2
7 < 9 – swap
9
4 7
1 2
Take 9 off – replace with 2
2
4 7
1
2 < 4 – swap them
4
2 7
1
4 < 7 – swap them
7
2 4
1
Take 7 off – replace with 1
1
2 4
1 < 4 – swap them
4
2 1
Take 4 – replace with 1
1
2
1 < 2 – swap them
2
1
Take 2 – replace with 1
1
Take 1
Sorted list voila.