ヒープを使用してO（1）空間でk-messed-arrayソートを行うことができます

Question

配列内のすべての要素が正しい位置から左または右のk番目の位置にあるというよく知られた問題では、最小ヒープ実装は次のとおりです。

サイズk + 1の最小ヒープを作成します。したがって、最小ヒープのルートはソートされた配列の最小要素の です。残りのn-（k + 1） 要素の場合、各反復では、すでにヒープにある要素[i]と の間で選択されます。したがって、ヒープに[i]を挿入し、 をheapifyし、minを抽出します。これにより、ソートされた配列の要素[i-k] が読み込まれ続けます。

時間の複雑さ：O（K）+ O（NK）の.log（K）

スペースの複雑さ：O（k）は

私の質問は：これは、O（1を使用して行うことができます）空間の複雑さ？

私はアプローチhereを見つけましたが、それを感知できませんでした。誰かが詳しく説明できますか？

これを行うことができます。遠端から開始し、min-heapの代わりにmax-heap を使用してください。 2k要素の最後のブロック を埋め込みます。最初に抽出された要素を変数に格納します。後続の 要素は、 ヒープソースと同様に、ヒープ構造を含む2kの最後の ブロックの直前に空いた位置に移動します。ブロックが1つだけ残っている場合は、それを適切な場所に置き換えます。最終ブロック 最終ブロックを最初の ブロックに「回転」させるには、O（n）回のパスが必要です。回転は簡単ではありませんが、O（n）とO（1） スペースで実行できます。

Answer 1

基本的な考え方は、配列にヒープを格納し、それを使用して配列の残りの要素をソートし、ヒープ部分自体をソートすることです。

ここでは分かりやすい分かりやすいヒープを使用したバリアントです。

1. アレイの最初のk+1要素を適所に浮遊させます。ヒープの最小要素は配列全体の最小値です。

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

2. スワップソートされていない部分と再heapifyの最初の要素とヒープの最小要素。

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

3. 未処理の要素がなくなるまで、手順2を繰り返します。この時点で、ヒープには配列の最大要素のk+1が含まれ、残りの要素はソート順になります。

   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