使用二進制堆合併多個數組

給定k個排序的整數數組，每個數組包含未知的正數元素（不一定是每個數組中的元素數相同），其中所有k個數組中的元素總數爲n，給出一個算法將k個數組合併成一個包含所有n個元素的有序數組。該算法的最壞情況時間複雜度應該是O（n∙log k）。使用二進制堆合併多個數組

2011-03-26 Alex

給定k個家庭作業任務，每個未知難度（不一定是不同），其中所有k個作業任務的總難度爲n，通常自己做家庭作業通常是有益的。 – quasiverse 2011-03-27 00:46:59

爲了保護OP，作業標籤由不同的用戶添加（可能是推測性的）。 – dsg 2011-03-27 01:00:53

啊..是的，好點...還是，它可以做作業... – quasiverse 2011-03-27 02:39:33

命名k-sorted列表1，...，k。

讓A成爲組合排序數組的名稱。

對於每個列表，我彈出v關閉i並將(i, v)分成最小堆。現在堆中將包含每對列表中最小條目的值對和列表ID。

雖然堆不是空的，但從堆中彈出(i, v)並將v附加到A。彈出下一個項目關閉列表i（如果它不是空的）並將其放入堆中。

還有n從堆中增加和刪除。堆每個時間步最多包含k個元素。因此運行時間是O(n log k)。

2011-03-27 00:03:53 dsg

沒有更多的補充。 – 2011-03-27 02:16:06

偉大的解決方案！但是，每一步的堆積操作呢？我認爲時間複雜度將會是O（nk logk） – Hengameh 2015-06-03 11:26:27

也許只是不變的是，堆包含數組中未被清空的最小元素。當你嘗試從列表中彈出一個項目時，如果這個列表是空的，你繼續從堆中彈出元素。

2013-06-23 13:34:52 stringofquarks

回答