WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H. The function is executing a binary search on a path of a heap.

Assumption: We have the specific path because it starts on the last available leaf which is the last index in the array that doesn't contain any value, and there is only one path to the top from there. Returns the specific index where we should put variable X. The main idea is to achieve time complexity of O(loglogN) to know exactly the index of the place to put X.

Implementation of the heap: The element at index i has children at indices 2i
and 2i + 1 and parent at index floor((i) ∕ 2).

The problem is, I don't really sure how should I define 'Mid' using 'Low' and 'High'.

EDIT: I think I found the formula:

$Mid$ = $Floor(High/2^{Floor(Log(High/Low)/2)})$

Maybe it is an easy arithmetical problem.

Example(In the picture): While executing WhereTo(X), I want a binary search to start on the yellow path (next available slot from the leaf to the root and the mid to be 14 or 7 (at the beginning) and of course to be updated in every iteration

Thanks a lot for the help.

  • $\begingroup$ What is the setup? What is the input of the function WhereTo? What is the expected output? It is a complete binary tree? How is the complete binary tree specified? It looks like you have become so familiar with the problem it did not occur to you that others are not. $\endgroup$ – John L. Apr 3 '19 at 16:41
  • $\begingroup$ "returns the specific index where we should put variable X" .X is an integer (It's minimum heap, of course it is a number) . The heap is represented by an array (there is one-to-one function between a heap represented by a binary tree to a heap represented by an array). $\endgroup$ – Yar.G Apr 3 '19 at 17:07
  • $\begingroup$ You can't know where to binary search without knowing the path to binary search. This path will take $\log(n)$ time to find. So your algorithm would end up begin $O(\log n)$ anyway. For instance, in your max heap example, the path would not be $\{16, 14, 7, nil\}$, but rather $\{16, 14, 8, 4\}$. You would not sift $7$ up before sifting $8$ up. $\endgroup$ – ryan Apr 3 '19 at 18:26
  • $\begingroup$ If I start from the leaf 'Open Slot' (lets assume I have pointer to there- O(1)) and I know there is only one path to the root. so I have to figure how I'll get the full path (indexes of path) to apply a binary search. Maybe this method is wrong but I know for sure I can achieve O(log log N) for this problem (maybe by useing more space?!) $\endgroup$ – Yar.G Apr 3 '19 at 18:39
  • $\begingroup$ @Yar.G Please edit the question to specify exactly how your heap is implemented. Is it this common implementation where "the element at index i has children at indices 2i + 1 and 2i + 2 and parent at index floor((i − 1) ∕ 2)"? $\endgroup$ – John L. Apr 3 '19 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.