# Difference between revisions of "TADM2E 4.14"

(Recovering wiki) |
(Recovering wiki) |
||

Line 2: | Line 2: | ||

The elementary algorithm compares the heads of each of | The elementary algorithm compares the heads of each of | ||

− | the | + | the <math>k</math> sorted lists to find the minimum element, puts this in the sorted |

list and repeats. | list and repeats. | ||

− | The total time is | + | The total time is <math>O(k n)</math>. |

Suppose instead that we build a heap on the head elements of each | Suppose instead that we build a heap on the head elements of each | ||

− | of the | + | of the <math>k</math> lists, with each element labeled as to which list it is from. |

− | The minimum element can be found and deleted in | + | The minimum element can be found and deleted in <math>O(\log k)</math> time. |

− | Further, we can insert the new head of this list in the heap in | + | Further, we can insert the new head of this list in the heap in <math>O(\log k)</math> |

time. | time. | ||

− | An alternate | + | An alternate <math>O(n \log k)</math> approach would be to |

merge the lists from as in mergesort, | merge the lists from as in mergesort, | ||

− | using a binary tree on | + | using a binary tree on <math>k</math> leaves (one for each list). |

problem | problem |

## Latest revision as of 18:22, 11 September 2014

Scan through all k lists in any order and use the stream of elements to build a heap of k elements. Since bubble_down works in O(logk) for a heap of k elements, we thus solve the problem in O(nlogk).

The elementary algorithm compares the heads of each of the $ k $ sorted lists to find the minimum element, puts this in the sorted list and repeats. The total time is $ O(k n) $. Suppose instead that we build a heap on the head elements of each of the $ k $ lists, with each element labeled as to which list it is from. The minimum element can be found and deleted in $ O(\log k) $ time. Further, we can insert the new head of this list in the heap in $ O(\log k) $ time. An alternate $ O(n \log k) $ approach would be to merge the lists from as in mergesort, using a binary tree on $ k $ leaves (one for each list). problem