0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I don't think I understand what you're asking. Could you be more specific? $\endgroup$
    – quicksort
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 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
    Commented Feb 11, 2017 at 16:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.