Heap sort algorithm

I have a heap made of a binary tree. Its not an array. I was wondering how would i go about sorting this. I know i need to take the last node and place it at the root and do a down heap bubble. This part i have. The problem I am having is knowing how to get the new last node. Is there an algorithm to find the last node开发者_C百科? Do i need to keep track of each of the parent nodes on each node?

Thanks.

Assuming the tree you start with is a full tree, I would see if you can keep track of the height of each node.

Then, when you iterate through the tree looking for the next child to remove you do a check at each node. If L.h > R.h go left, else go right. The only caveat I have on this idea is it means when you take that node you need to update all the heights. Which add a cost of O(log n). But since you're traversing down the tree which is theta(log n) it's not too big a deal asymptotically.