How to do binary search on a path in a binary heap

Question

I am trying to solve this question:

Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in time $O(\log(\log n))$.

My solution:

Before the loop, I will create a new linked list and initiate $heap[i]$ to be the first item in the list. Then, I will run a loop on the heap that will start from index $i$, and in every iteration, it will extract the parent of the item in the index $i$ to a new array and will break after extracting the root of the heap.

Then, I will use binary search on the new array (I know that every parent in the heap is bigger than its children. So the new array is already sorted). The problem is that the extraction of the parents cost me $O(\log i)$ which can be in the worst-case $O(\log n)$, and for that reason, my solution can't work.

I will be grateful for any help.

Answer 1

Note that a path from the root to $heap[i]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming 1ドル$ based indexing, the 1ドル^{st}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{2} \rfloor$ location in the array. The 2ドル^{nd}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{4} \rfloor$ location, and so on. Using it you can easily perform binary search on the path from root to $heap[i]$ in $O(\log \log n)$ time.

Pseudocode:

Assume that we have a min heap. Initialize, start = 1ドル$ and end = $h = \lfloor \log(i) \rfloor$

BinarySerach (start, end)
mid = (start + end)/2
index of mid = i/(2^(h- mid)) //(h-mid)^th ancestor of i
if (end-start = 1)
 if (heap[index of mid] == x) return "YES"; otherwise "NO".
if (heap[index of mid] >= x)
 return BinarySearch (start, mid)
else 
 return BinarySearch (mid+1,end)

• yuval: Hi, thanks for your answer. Even that i understand your answer, I have been struggling to develop this alghoritem you suggest , if you can write a pseudo code that doing this binary se search it will help me alot.
• Inuyasha Yagami: @yuval Can you tell where are you struggling? I can help with that.
• yuval: I tried to wrote a pseudo code and i can't see how to devide the path items each time (like in binary search where you dividing by 2). I mean, its a little long to explain everything i tried and i will be glad if you will just write for me a pseudo code of the iteration it will be less time for me and less time for you.
• yuval: I know it's important to solve things yourself but i solved a harder problems for sure i am just missing something and maybe see the solution is the right thing to do after putting somework on this thing
• Inuyasha Yagami: @yuval I have added the pseudocode. Let me know if there is any confusion.