可以使用堆在O（1）空間中完成k-雜亂陣列排序

Question

在熟悉的問題中，陣列中的每個元素至多在距離其正確位置的位置（無論是向左還是向右）最小堆實現如下。

創建大小爲k + 1的最小堆。所以，最小堆的根是排序數組的最小元素。對於其餘的n（k + 1） 元素，在每次迭代中，選擇位於[i]和已在堆中的元素之間。因此，將[i]插入堆， heapify，並提取最小。這將繼續填充已排序數組的元素[i-k] 。

時間複雜度：O（K）+ O（NK）.LOG（K）

空間複雜度：O（K）

我的問題是：可以這樣使用了O完成（1 ）空間複雜性？

我發現了一種方法here，但無法感覺它。有人能詳細說明嗎？

你可以在原地做到這一點。從遠端開始，並使用最大堆 而不是最小堆。在原地堆砌2k元素 的最後一塊。將第一個提取的元素存儲在變量中;隨後的 元素進入緊接在最終的 2k塊（其包含堆結構）之前空出的位置，類似於常規的 堆排列。當只剩下1個塊時，將其堆疊到位。需要O（n）通過最後的 以將最後的塊「旋轉」回到最初的 塊。旋轉不是微不足道的，但可以在O（n）和O（1） 空間中完成。

Answer 1

其基本思想是將堆存儲在數組中，使用它對數組的其餘元素進行排序，然後對堆部分本身進行排序。

這是一個使用min-heap的變體，可能更容易理解。

1. heapify數組中的第一個k+1元素，到位。堆的最小元素將是整個數組的最小值。

   k+1 | n-(k+1) 
   heap | unsorted 
   

2. 交換與未分選部和重新heapify的第一元件堆的最小元素。

   k+1 | 1  | n-(k+2) 
   heap | sorted | unsorted 
   

3. 重複步驟2，直到沒有更多未處理的元素。此時堆包含數組的最大元素，其餘元素按排序順序排列。

   k+1 | n-(k+1) 
   heap | sorted 
   

4. 排序陣列

   k+1   | n-(k+1) 
   sorted heap | sorted 
   

5. 移動排序堆到陣列的另一端的堆部分。該數組現在排序。

   n-(k+1)| k+1 
   sorted | sorted heap