heap sort

I absolutely agree that the person who developed the heap sort algorithm is a genius. Not only a complicated (well complicated for me, I’m just a simple-minded people) but it could have faster run time than other sorting method.

However, heap sort manipulates binary tree to do the sorting. I draft the tree in order to understand its complexity (and hopefully could at least memorize its algorithms). I take a sample of 15 random numbers and placed them in a binary tree. Then try to “heapify” (according to the tutorial solutions) the tree. It is actually quite simple; I just need to make sure that each root of the sub-trees is larger or equal than its children (by swapping the parent with the largest child). Then I faced the next step – “siftdown”. Argh, by simply delete off the root and push it in the array, then place the right-most node on the root. My “heapified” castle collapsed and I need to “reheapify” all over again.

I continued till I get the 4th largest number. I gave up. The whole A4 paper is full of trees and I messed up some nodes. Children become orphans. It is a messed. Fortunately I finally gasped its concept. Although I don’t know why it has faster run time, I will manage to answer some how.

P/S: Speacial thanks to cs.wisc.edu which makes my heap sort life easier.