GameDev.netHeapsort

Heap Sort
by Yin-So ChenBy viewing the array as a complete binary tree, Heap Sort transforms such a binary tree into a heap. This algorithm does not require overhead and is not recursive. The algorithm basically follows the following steps: - Sort the complete binary tree (actually an array) so that it becomes a max-heap, thus the first element is always the biggest element.
- Since what we want is exactly the opposite (the last element should be the biggest instead), we swap the first element and the last element.
- Now we have to re-sort the array (except the last element), so that the first element is again the biggest.
- Then we repeat the second step, so that the first element is swapped with the current last element.
- We repeat 2, 3 so that all the elements are sorted.
Such a strategy takes the advantage of binary tree. Every time we move an element, we move it to its current position's child. Thus it moves in a greater distance than Insertion Sort. Below is the pseudo-code of Heap Sort.
© 1999-2011 Gamedev.net. All rights reserved. |