0
$\begingroup$

Suppose you have two heaps each containing $2^k - 1$ elements.

Design an efficient algorithm for merging these two heaps into a single heap.

My approach was to assume two heaps are maxheap. Create one node with value $-\infty$ and attach one heap as left subtree and another as right subtree, and call the heapify procedure. So it should take $O(\log(2(2^k-1)+1))=\log(k)$ time.

But my confusion is $-\infty$ valued node doesn't necessarily go at the last node of heap.

Improve this question
$\endgroup$
1
  • $\begingroup$ last node of heap you seem to be implying a specific implementation of heap where there is a last node - an "implied binary heap" in an array comes to mind. But: A heap is not an ordered tree: the "least priority key" does not need to end up in any given position - any leaf will do. Combining two heaps implemented with links is trivial: select the highest priority key from both root nodes, remove it from its heap and create a new root node for the combined heap holding this key and having both "input heaps" as children. (Note that this doesn't necessarily keep "balance".) $\endgroup$
    – greybeard
    Commented Nov 27, 2016 at 15:42

1 Answer 1

Reset to default
1
$\begingroup$

Calling heapify once isn't going to build a heap in one iteration . Instead merge the two arrays which contain both heaps initially and call BuildHeap() procedure. You will get a heap in O(n) time.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.