How to insert into a binary max heap implemented a

Question

In a binary max heap implemented as a binary tree (where each node stores a pointer to its parent, left child, and right child), if you have the pointer to the root of the heap, how would you implement an insert operation? What's supposed to happen is the node first gets inserted as the last element in the last row. For array based, you could append to the array, but for tree based implementation, how would you find the right spot?

Answer 1

In this older question, I gave a short algorithm that uses the binary representation of the number k in order to find a way to select the k-th node out of a binary heap in a top-down traversal. Assuming that you keep track of the number of nodes in the explicit tree representation of the binary heap, you could do the following to do an insert operation:

1. Using the above algorithm, determine where the new node should go, then insert the node at that position.
2. Continuously bubble the node upward either by rewiring the tree to swap it with its parent or by exchanging the data fields of the node and its parent until the element is in its final position.

Hope this helps!

Answer 2

If you hang you new vertex under any leaf of your tree (as left or right successor, doesn't matter), and then repair the heap from this new vertex to the top (that is, regarding every other vertex with successors, swap it with the greater successor and climb up if needed), your new element will find it's rightful place without breaking the heap. However, this will only guarantee you that every other insert operation will take O(h) time, where h is the maximum height of the tree. It's better to represent heap as an array, obviously, because that way it's guaranteed that every insert operation will take O(logN) time.

Answer 3

To find the exact location as to where the new node is supposed to be inserted, we use the binary representation of the Binary Heap's Size. This takes O(log N) and then we bubble it up which takes O(log N). So the insertion operation takes O(log N)... For a detailed explanation check out my blog's post on Binary Heaps -

http://theoryofprogramming.com/2015/02/01/binary-heaps-and-heapsort-algorithm/

I hope it helped you, if it did, let me know...! ☺