Design-and-analysis-of-algorithms-heapify-method

DAA-ヒープ化メソッド

Heapifyメソッドは、 i ^ th ^ 要素の左右のサブツリーがヒーププロパティに従う配列の要素を再配置します。

Algorithm: Max-Heapify(numbers[], i)
leftchild := numbers[2i]
rightchild := numbers [2i + 1]
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i]
   largest := leftchild
else
   largest := i
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest]
   largest := rightchild
if largest ≠ i
   swap numbers[i] with numbers[largest]
   Max-Heapify(numbers, largest)

指定された配列がヒーププロパティに従わない場合、ヒープは次のアルゴリズム Build-Max-Heap（numbers []） に基づいて構築されます。

Algorithm: Build-Max-Heap(numbers[])
numbers[].size := numbers[].length
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1
   Max-Heapify (numbers[], i)