Timeline for Merging sorted arrays stored as linked lists
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2021 at 19:58 | vote | accept | Redman | ||
| Oct 4, 2021 at 22:43 | comment | added | Yuval Filmus | Operations on a heap take logarithmic time. | |
| Oct 4, 2021 at 21:53 | comment | added | Redman | yes. First i construct heap temp with first elements of all lists and it has same size of number of lists. Then i pop min value and itβs index in temp heap. Add min value to array A. Then get next value in list π΄πππππ₯. And add this value to heap temp. And i keep looping for above steps until n. Where am i going wrong? | |
| Oct 4, 2021 at 21:03 | comment | added | Yuval Filmus | Use a heap instead of an array to store the $k$ smallest elements at every step. | |
| Oct 4, 2021 at 21:01 | comment | added | Redman | Please see my updated question. I think i get the runtime as O(k) and not logk | |
| S Sep 30, 2021 at 14:39 | history | suggested | Nitin Verma | CC BY-SA 4.0 |
i think he meant merge-sort instead of quick-sort
|
| Sep 30, 2021 at 8:45 | review | Suggested edits | |||
| S Sep 30, 2021 at 14:39 | |||||
| Sep 30, 2021 at 5:40 | history | answered | Yuval Filmus | CC BY-SA 4.0 |