heap data structure via pointers

Question

Suggest an efficient way to find last position in heap satisfying the following conditions:

1) via pointers not via array

2) where we can insert or delete node

I could find it in O(n) time complexity but suggest a way which is of O(logn) or O(1) time complexity.

Answer 1

I'm assuming here that you mean a binary heap.

If you know how many nodes are in the heap, you can find the last node in O(log n) time by converting the count to binary, and then following the path of bits from high to low. That is, take the left node if the bit is 0, and the right node if the bit is 1.

For example, if there are three nodes in the heap, the binary representation of the count is 11. The root is always the first node, leaving you with 1. Then you take the right branch to get the last node.

Say there are 5 nodes in the heap:

       1
    2     3
  4   5

In binary, that's 101. So you take the root. The next digit is 0 so you take the left branch. The next digit is 1, so you take the right branch, leaving you at node 5.

If you want the next available slot, you add 1 to the count and do the same thing. So 6 would be 110. You take the root, then the right branch, and the left child of 3 is where you'd add the new node.

You can do the same kind of thing with any d-ary heap, except that instead of converting to binary you convert to base d. So if your heap nodes each have up to three children, you'd convert the count to base 3, and use essentially the same logic as above.

An alternative is to maintain a reference to the last node in the heap, updating it every time you modify the heap. Or, if you want to know where the next node would be placed, you maintain a reference to the first node that doesn't have two children. That's O(1), but requires bookkeeping on every insertion or deletion.