1
$\begingroup$

Is there a known algorithm that can reorder a binary heap of size $N$ so that after the reordering

  • we still have a valid binary heap
  • the first half of the input ($\frac{N}{2}$ elements) are all placed in one half (not necessarily sorted)
  • worst case linear time for all inputs
  • without extra memory
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Wouldn't quickselect followed by bottom-up heap construction do it? $\endgroup$
    – Pseudonym ♦
    Commented Aug 3 at 14:04
  • $\begingroup$ No. Quickselect has N^2 worst case. $\endgroup$
    – user172776
    Commented Aug 3 at 15:23
  • 4
    $\begingroup$ How about quickselect with median of medians? $\endgroup$
    – Li-yao Xia
    Commented Aug 3 at 19:59
  • $\begingroup$ This might do the job: people.csail.mit.edu/rivest/pubs/BFPRT73.pdf $\endgroup$
    – Pseudonym ♦
    Commented Aug 3 at 23:42
  • $\begingroup$ @Pseudonym This algorithm will work and I already read about it before. But, as you can see, it has a high constant factor and additionally needs a final heapify. I hoped, since the heapify already quite near approximates the task and still keeps the heap data structure, that some algorithm for a clean tree adaption exists, that solves it. $\endgroup$
    – user172776
    Commented Aug 4 at 3:49

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.