retagged by
411 views
1 votes
1 votes
  1. Design an algorithm to construct one heap that contains all the elements of two given heaps of sizes n and m, respectively. The heaps are given in a linked-list representation ( each node has links to its two children). The running time of the algorithm should be O(log(m + n)) in the worst case
retagged by

1 Answer

0 votes
0 votes
We take the last element of one of the heaps and add it to the root and connect the two heaps to it. Now apply heapify on the resulting tree which takes O(log(m+n)) (in the worst case) to settle the root to its correct position.

Related questions

0 votes
0 votes
1 answer
1
syedasafoora asked Nov 8, 2023
222 views
Consider the following algorithm for Build-Max-heap and the given array A=[ 47,96, 35, 54, 77, 65, 83]. Run this algorithm on the given array and redraw the heap and the ...
0 votes
0 votes
1 answer
2
amitarp818 asked Nov 28, 2023
570 views
Consider the following array of elements<96,42,50,17,15,5,7,11,39,23,6,9,19,100,12>The minimum number of interchanges using buildheap needed to convert it into a max heap...