Heapsort question

As a heap is a combination of a binary tree and array, when sorting does the entire heap keep the form of a complete tree开发者_开发知识库?

For a homework assignment, I have to trace out the heap and array for each step of the sort, and I'm not sure of the tree representation.

---

A heap is always a perfectly-balanced fully-populated tree that follows the Heap Invariant- for a min-heap, a node's value is always greater than or equal to the value of each of its children.

Heapsort creates a heap out of unsorted data (O(n) time), then repeatedly removes the top element of the heap (O(lg n) time because the heap has to be maintained with each removal) and puts it into an array. Notably, this only works if it keeps the heap invariant- which requires, among other highlights, perfect balancing and a valid tree.

The binary tree isn't the most efficient representation of a heap; the Wikipedia article on binary heaps explains very well how to use an array to represent one. The article on Heapsort mentions a useful detail: you can sort in place, by using the space off the end of the heap, if using the array representation, to build your output array, because the heap always balances and removing an element will eventually free up the physically last cell of the array representing the heap.