Heap Sort - max heap

Question

I have a list of numbers in [17,98,89,42,67,54,89,25,38] which is to be inserted in an empty heap from left to right . what will be the resulting heap ?

Answer 1

Although this isn't the heap sort algorithm (sorts a data set by using heap), building a heap does require some comparison work to ensure it remains a heap (you're wanting a max heap, so all children are less than their parent). The way to build a max heap is to put the newest element in the next available spot (the left-most spot in the tree not filled within the deepest row, or starting a new row from the left-most spot). Once an element is inserted it is swapped with its parent if it's bigger than its parent until it either becomes the root of the tree or finds a parent bigger than itself. This is done until all elements are inserted, and it, in fact, has the max element as the root.

It is important to note that for a min heap, the minimum element is the root, so instead of having all parents bigger than their children, it becomes all children bigger than their parent. In building a min heap, still add new vertices to the same spot, but switch the new child with their parent if the child is less than the parent instead of more.

Two images have been attached with the resulting max & min heaps. Note that 89a corresponds to the first 89 and 89b corresponds to the seconds, for clarification purposes. Max Heap Min Heap