How to insert into a binary max heap implemented as a binary tree?
In 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 a pointer to the root of the heap, how would you implement an insert operation? Suppose node is first inserted as the last element of the last row. For an array, you can add to an array, but for a tree based implementation, how would you find the right place?
source to share
In this older question, I gave a short algorithm that uses the binary representation of the number k to find a way to select the kth node from the binary heap in a downward traversal. Assuming you are keeping track of the number of nodes in an explicit tree representation of the binary heap, you can do the following for an insert operation:
- Using the algorithm above, determine where the new node should go, then insert the node at that position.
- Continuously bubble a node up, either by reassigning the tree to swap it with its parent, or by swapping data fields between the node and its parent until the element is at its final position.
Hope this helps!
source to share
If you hang a new vertex under any leaf of your tree (how the left or right successor does not matter) and then restore the heap from that new vertex to the vertex (that is, in relation to every other vertex with successors, swap it with a larger successor and , move up if necessary), your new element will find its rightful place without breaking a bunch. However, this only ensures that every other insert operation will take O (h) time, where h is the maximum tree height. It's better to think of the heap as an array, obviously, because that way it ensures that each insert operation takes O (logN) time.
source to share
To find the exact location relative to where the new node should be inserted, we use a binary representation of the binary heap size. This takes O (log N) and then we bubble it up, which takes O (log N). So an insert operation takes O (log N) ... For a detailed explanation, check out my blog post on binary heaps -
http://theoryofprogramming.com/2015/02/01/binary-heaps-and-heapsort-algorithm/
Hope this helped you, if yes let me know ...! ☺
source to share