Assuming I want to insert a node into a binary heap, how can i find the index of the node in the heap after the insertion and the heapifying? The binary heap is represented as an array. I need to find this algorithm in O(log(log(n)).
I know how to find it in log n complexity but does not succeed to find it in log log n.
Thank you all.
Let's take a look at how a node is usually inserted. It is appended to the end of the array and then it is swapped with its parent until it reaches the root or becomes greater then or equal to its parent(I assume that we have a min-heap). That's why we just have to find a position of this element in the path from it to the root. But this path is sorted(due to the properties of a heap). That's why we can use binary search to find its position in this path. The length of the path is O(log n), so the binary search works in O(log(log n)).