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))$.
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.