排序K-排序陣列具有最小堆

Question

很好的解決排序的k排序陣列（每個元素是至多爲k從其目標位置離開）是，

1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time. 

2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements. 

overall complexity will be O(k) + O((n-k)*logK) 

我無法理解的相關性的數組進行k分類以使用堆技術。即使數組沒有進行k分類，這種方式是否還能工作？

Answer 1

因爲當數組未被k分類時，這不起作用。

因爲排序後的第一個元素總是第一個k + 1元素中的最小元素，依此類推。

@leventov向我們展示了一個例子。

Answer 2

答：得到k最小數（不一定排序）從一個數組：
你認爲該方法將在O(k) + O((n-k)*logK)時間正常工作。

B：排序所述陣列：
你找到大小爲k的堆的最小數目在每個步驟，但是如果從陣列的最小數目位於索引k + 2？
只有在你的算法的第一步中才能得到它，直到你插入它時，你會輸出2個數字，爭辯說它們是原始最小值的<。

因此，您肯定希望讓他們從排序位置移動not more than k。