The order does not matter! When you keep feeding a max heap with N values (replacing the root and heapifying if the value is smaller than root) in this case the sums, you end up with the least k sums encountered. And the root would be the kth sum in increasing order. We feel all n*m values and order doesn't matter. Only, this algo doesn't take advantage of the sorted property of the 2 inut arrays.
On Mon, Sep 14, 2009 at 11:16 PM, ankur aggarwal <ankur.mast....@gmail.com>wrote: > *"For each of the n*m sums add it to the heap (if it ain't full with k > elements) or replace the root and heapify if the sum is lesser than the > root."* > how u can judge which is the next value to be added.. > > try your algo at > > array a 1 2 3 4 5 7 9 > and array b 2 3 5 6 7 > > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
