HeapSort.java
We have studied a few in place sorts that turn random order array into its lowest entropy state -- totally aligned array -- with the cost of time and space.
These in place sorts, insertion sort, selection sort and shell sort, are interesting, because they have small memory footage -- they don't need extra stack to hold pending states during recursive divide and conquer, they also don't need extra array to hold intermediate results. All they need is the array it is trying to sort and one variable for swamp.
Insertion sort and selection sort have O(n^2) time complexity, while shell sort is an improved selection sort. Using shell sort, the elements bubble up quicker sometimes with larger move steps and can achieve O(nlogn) performance at best case. With the memory resource limitation, can we do the sorting faster?
Maybe, if we spent time to build a tool to facilitate the sort. If time spending on building the tool is not outrageous, the tool might change the game rule, and we saves time in the later long journey of sorting.
We can build a binary heap, a data structure where the keys are stored in an array such that each key is guaranteed to be larger than or equal to the keys at two other specific positions.
In a heap, the parent of the node in position k is in position [k/2], the two children of the node in position k are in positions 2k and 2k + 1. We can travel up and down a heap by array index arithmetic. k/2 move us up the heap, while 2k or 2k + 1 move us down the heap. For the math to work, the heap's array index start from 1 instead of 0.
 |
| heap represented as array |
For insert, we add the new key at the end of the array, and then swim up through the heap with that key to restore the heap condition.
For delete, we take root node off the top, put the item from the end of the heap at the top, and then sink down through the heap with that key to restore the heap condition
Feel the algorithm
0
1
2
3
4
5
6
7
8
9
10
11
function exch(a, i, j) {
var t = a[i];
a[i] = a[j];
a[j] = t;
}
//heap: parent node is bigger than any of the child node
function sink(a, k, N) {
while (2*k < N) {
var j = 2*k;
if (j < N && a[j] < a[j+1]) j++;
if (a[k] >= a[j]) break;
exch(a, k, j);
k = j;
}
}
function sort(a) {
N = a.length;
//build a heap, root at a[1], child of a[i] is at a[i*2] and a[i*2 + 1]
for (var k = Math.floor(N/2); k >= 1; k--) {
sink(a, k, N);
}
N --;
while (N > 2) {
exch(a, 1, N--); //remove heap head node (put at array end)
sink(a, 1, N); // fix heap
}
//fixing a[0]
for (var j = 1; j < a.length && a[j] < a[j-1]; j++) {
exch(a, j, j-1);
}
}
Heapsort has time complexity NlogN, it is a in place sorting algorithm, the space complexity is O(1).
<Prev Next>
