Heapsort - Percolate-down/Shift-down操作とHeapify操作の違い/関係は何ですか？

Question

Percolate-down/Shift-down操作とHeapify操作の違いは何ですか？

これはCのShift-down関数です。このコードを使用してHeapsortを実装しました。

void IterativeShiftDown(int i) 
{ 
    int leftOrRightChildIndex = EMPTY; 
    int currentIndex = i; 
    int currentElement = EMPTY; 
    int childElement = EMPTY; 

    while(HasAnyChild(currentIndex)) 
    { 
     if(HasBothChild(currentIndex)) 
     { 
      if(GetLeftChildElement(currentIndex) > GetRightChildElement(currentIndex)) 
      { 
       leftOrRightChildIndex = GetLeftChildIndex(currentIndex); 
      } 
      else 
      { 
       leftOrRightChildIndex = GetRightChildIndex(currentIndex); 
      } 
     } 
     else if(HasLeftChild(currentIndex)) 
     { 
      leftOrRightChildIndex = GetLeftChildIndex(currentIndex); 
     } 

     currentElement = GetElement(currentIndex); 
     childElement = GetElement(leftOrRightChildIndex); 

     if(currentElement < childElement) 
     { 
      SwapElements(currentIndex, leftOrRightChildIndex); 
     } 

     currentIndex = leftOrRightChildIndex; 
    } 
} 

このコードを使用してHeapify（）関数を作成できますか？

はいの場合はどうですか？

また、Heapifyを使用してHeaportを実装するアルゴリズムとは何ですか？

Answer 1

シフトダウンは、典型的には、既存のヒープに項目を挿入する動作です。

heapifyは、通常、順序付けられていないデータからヒープを作成する操作です。

は、アレイに実装されるようそれが原因ヒープの性質の途中で開始

... perreal供給機能を拡張します。ヒープ内のインデックスNからの各子要素はN * 2またはN * 2 + 1であるため、要素の最後の1/2には子がありません。さらに、ヒープ内のノードの子ノードは、親ノード（一貫して大きいか小さいかなど）との関係がありますが、互いに関係はありません。したがって、葉の子ノードを交換する必要はありません。

したがって、必要に応じて各要素を途中で吹き飛ばし/篩い分けすることから開始します。

ヒープが大きい場合があります。具体的には、データを取得しながら（async disk reads/db gets）CPUの処理を無償で行えるように入力を受け取っている場合、ヒープをほぼ無料で段階的に構築することができます。

これらの行に沿って、データを取得したら、UIを作成したり、結果を少しずつフィードバックしたりすることができます。すぐに初期結果が得られます。

世界でデータをソートしたのは最速ではありません。しかし、（私が懸念している限り）アルゴリズムの処理段階だけでなく、入力=>出力段階で並べ替えのコストを償却する最良の方法です。これはしばしば便利です。

Answer 2

はい、基本的にすべての項目をシフトダウンすることができます。 Followingはウィキペディアからのものである：

function heapify(a, count) is 
    (start is assigned the index in a of the last parent node) 
    start := (count - 1)/2 
    while start ≥ 0 do 
     (sift down the node at index start to the proper place such that all nodes below 
      the start index are in heap order) 
     siftDown(a, start, count-1) 
     start := start - 1 
    (after sifting down the root all nodes/elements are in heap order)