2 votes 2 votes 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. Algorithms merging algorithms + – VIKAS TIWARI asked Dec 13, 2017 VIKAS TIWARI 3.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply srivivek95 commented Dec 13, 2017 reply Follow Share Here, you can relate it with the Huffman's coding. Try solving as if these file length are the frequencies for the character (there,Huffman coding). You can draw the Huffman tree & then the sum of all all nodes (consider nodes which are the result of sum of two file length) will give the optimal merge complexity. http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/ 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes According to optimal merge pattern we take two minimal and merge it so given sequence is: f1 99 f2 27 f3 71 f4 199 f5 259 we arrange sequence in ascending order f2, f3, f1, f4, f5 M1: Merge f2 and f3 :: 27+71 = 98 M2: Merge M1 and f1 :: 98+99 = 197 M3: Merge M2 and f4:: 197+199 = 396 M4 Merge M3 and f5:: 396+259 = 655 VIKAS TIWARI answered Dec 13, 2017 • selected Jan 5, 2018 by VIKAS TIWARI VIKAS TIWARI comment Share Follow See all 0 reply Please log in or register to add a comment.
