Build Heap And Heapsort Without Array

[tigerman33]

Hi,

if you already have a binary tree, you should be able to transform it into a heap by successively performing a so-called sift operation on the nodes from the bottom up. A sift operation means exchanging the given node with the tree root. Then if necessary, you exchange that node with the larger one of its two sons to keep the ordering. After that, recursively repeat on the just-changed subtree, until the node is at its correct position.
If I remember right, it should actually be enough to do this on only the bottom half of the tree, but I'm not going to give you any guarantuee on that one...

I would suspect Wikipedia has an article on this operation, given that there seems to be one on the heapsort algorithm itself.

Hope this helped.