For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method.

Incremental method: enter image description here

In-place method: enter image description here

Is there a way to build heap using decision tree for inputs of size 4 that uses fewer decisions in the worst-case, compared to above methods?

Notes on heap: https://drive.google.com/open?id=0By6GDPYLwp2cY3lfbEVWNHlrSlE Incremental method - page 36, In-place method - page 48.

  • 1
    $\begingroup$ I don't think I understand what you're asking. Could you be more specific? $\endgroup$ – quicksort Feb 11 '17 at 15:29
  • $\begingroup$ Every branch in above methods makes a comparison to built a heap. So, is there any other algo. that makes fewer comparison to built a heap? $\endgroup$ – New_Coder Feb 11 '17 at 15:42
  • $\begingroup$ When $a_1$ and $a_3$ are less-than $a_2$ and $a_4$, your upper decision tree won't compare $a_1$ to $a_3$, so are your leaves just a rough idea of the heap? ​ ​ $\endgroup$ – user12859 Feb 11 '17 at 16:05

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.