explain this process. how do you make sure it's in the correct order? and what order is correct? a comparison sort cannot be faster than nlogn. so how are you getting logn for the entire deletion process if the sort alone is nlogn?

The process is:

For example, if you replace the root of a max heap

lets say the old root was n and its children are n1 and n2

if you replace n with the lowest level last entry n3 and n3 >= n1 && n2, then you can just stop

however, if replacing n with n3 means that n1 or n2 is suddenly >= n3, then you have to swap it with the LARGER of the 2 children until it satisfies the heap property you want (in this case, max heap?)

apparently there is an algorithm called the max-heapify function which is used here

how do you know that you can just stop? how do you know there isn't some n4 which is greater than the rest?

This post was edited by carteblanche on Feb 4 2013 12:20am

Assuming you made the max heap correctly, you would have made it so that each child was less than or equal to the parent. Therefore no node n the lowest level could possibly be larger than the original root. (after an initial sift)

However, in the case that you replace the root with some new node, the worst case scenario would be to swap it with its child on each level until the last level. An entire other sort doesn't seem like it would be necessary

The whole point of forcing this constraint is to speed up the sort. So, do you understand the answer to your original question and why that answer is correct?

yeah it makes sense. As far as the actual math and how some aspects are coded I am still unsure (I am not in the algorithms class yet lol, was just reading stuff about heaps online for hobby) but conceptually it makes sense. Forcing the constraint to speed up the sort is pretty ingenious.