The Heap Sort By Samuel Marateck (c) 2000 The definition of a heap is a complete binary tree in which the value stored in the parent is greater than or equal to that stored in each of its children. Although a tree is used to explain how a heap works, the program uses an array to represent the heap. All operations are done on the array. The heap sort starts with a tree that's a heap. We will work with the following initial example with N, the number of nodes equal to 6: r / \ p m / \ / o k c The initial array configuration corresponding to this is: rpmokc. We exchange the root with the last node on the tree, c. c / \ p m / \ / o k r The r is now in its proper place in the sorted array: cpmokr. So we set N to 5, therefore working only with cpmok, and the tree representing the heap becomes: c / \ p m / \ o k The tree, however, is no longer a heap. We see which of c's children is the larger, here it's p, and swap it with c. So the tree is now: p / \ c m / \ o k It's still not a heap. We continue down the subtree which has c as its root. The reason we don't have to worry about the subtree with m as its root is that that subtree is already a heap. We see which of c's children is the larger, here it's o, and swap it with c. So the tree is now: p / \ o m / \ c k This process is called reheapification. The tree is now a heap and the corresponding array, including the r is pomckr. Next we exchange the root p with k k / \ o m / \ c p The array is now komcpr. The p and r are now in their proper place in the array. So we set N to 4 and the tree becomes k / \ o m / c Reheapification yields o / \ k m / c We exchange the root o with the last node on the heap and get c / \ k m / o The array is now ckmopr. Now the opr are in their proper place in the array. So we set N to 3 and deal with c / \ k m Reheapification yields m / \ k c After the exchange we get c / \ k m The array becomes ckmopr and mopr are in their proper place in the array. Set N to 2 and the tree becomes: c / k Reheapification yields k / c The exchange produces c / k and the array becomes ckmopr and the sort is finished. The time analysis for reheapification is O(logN) since it depends on the number of levels in the tree. Since there are N items in the list, an upper limit for heap sort is O(NLogN).