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?
3
votes
What is the shape of this linked list? If parents can't necessarily point to their children, then in what order are the nodes linked?
- templatetypedef
The linked list will look like this en.wikipedia.org/wiki/Binary_heap So each node, will have a pointer to its parent, left child, right child and the key value. Null if it is the root or doesn't have the children.
- omega
@omega- Oh, okay. That's not a doubly-linked list representation of a binary heap; that's a tree representation.
- templatetypedef
yeah but isn't doubly the same thing, because you have pointers going both ways (parent to child, and child to parent)?
- omega
@omega- They have the same representation, but a doubly-linked list is a very different structure than a general tree structure. A doubly-linked list is a special case of a tree where each node points to its children and to its parent, so it would be incorrect to describe the tree representation as a linked list.
- templatetypedef
3 Answers
1
votes
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:
- Using the above algorithm, determine where the new node should go, then insert the node at that position.
- 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!
1
votes
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.
0
votes
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...! ☺
