Search code examples
arraysalgorithmdata-structuresbinary-heap

Finding node's postion in array(as binary heap)

Assuming I want to insert a node into a binary heap, how can i find the index of the node in the array that representing the heap after the insertion and the heapifying? I need to find this algorithm in O(log(log(n)).

Thank you all.

Solution

  • If you look at the insertion in a binary heap, the new node is put at the end, then moves upward his branch to find its rightful place.

    So, as you know the size of the heap, you know in which branch the new node will be inserted. The branch size is log(n). From this position, you can also find all of the nodes belonging to the branch.

    All you have to do is a binary search along this branch, and you'll find the place of the new node in log(log(n)).