Register

Why we take min heap in optimal merge pattern

• retagged by
615 views

2 Answers

0 votes
0 votes
To select Min at Each iteration in O(1) time

it is best Datastructure suited for this job
User Avatar
0 votes
0 votes

In optimal merge pattern we Pick always two Minimam element.  And min heap is best data structures if we want always Minimam element. Like  optimal merge, Huffman coading, kruskal. 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
Ali Jazib Mahmood asked Aug 18, 2017
1,446 views
Optimal Merge Pattern,similar to http://gateoverflow.in/1997/gate2014-2-38
To merge 2 files of size m and n it takes m + n time What will be the optimal time Complexity to merge the files of size 10, 15, 40, 70, 75 and 80?
To merge 2 files of size m and n it takes m + n time What will be the optimal time Complexity to merge the files of size 10, 15, 40, 70, 75 and 80?
User Avatar
2 votes
2 votes
1 answer
2
VIKAS TIWARI asked Dec 13, 2017
3,992 views
Optimal Merge Pattern
Given a set of sorted files f1,f2,f3,f4,f5 of lengths 99,27,71,199,259 we need to merge these files into a single sorted file Using Optimal Merge Pattern.
Given a set of sorted files f1,f2,f3,f4,f5 of lengths 99,27,71,199,259 we need to merge these files into a single sorted file Using Optimal Merge Pattern.
User Avatar
5 votes
5 votes
1 answer
3
Shashank Chavan asked Dec 15, 2015
2,226 views
In Optimal merge pattern when do we get more than one tree?
In Optimal merge pattern when do we get more than one tree(Sub trees) when creating a merge pattern? Can you explain/draw optimal merge tree for n=7, <8,15,3,10,20,2,30>
In Optimal merge pattern when do we get more than one tree(Sub trees) when creating a merge pattern?Can you explain/draw optimal merge tree for n=7, <8,15,3,10,20,2,30>
User Avatar
0 votes
0 votes
2 answers
4
radha gogia asked Jul 31, 2015
11,709 views
A average number of comparison performed by the merge sort algorithm ,In Merging two sorted lists of length 2 is
If I have two lists of length 2 then no of comparisons in the worst case would be 2 only , since If I have say 10,20 in list A and 5,7 in list B so then on merging 10 is ...
User Avatar
Link Copied!