Design-and-analysis-of-algorithms-extract-method

提供:Dev Guides
2020年6月22日 (月) 22:56時点におけるMaintenance script (トーク | 投稿記録)による版 (Imported from text file)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

DAA-抽出メソッド

抽出メソッドは、ヒープのルート要素を抽出するために使用されます。 アルゴリズムは次のとおりです。

Algorithm: Heap-Extract-Max (numbers[])
max = numbers[1]
numbers[1] = numbers[heapsize]
heapsize = heapsize – 1
Max-Heapify (numbers[], 1)
return max

前述の同じ例を考えてみましょう。 次に、要素を抽出します。 このメソッドは、ヒープのルート要素を返します。

メソッド

ルート要素を削除すると、最後の要素がルート位置に移動します。

ルート要素

これで、Heapify関数が呼び出されます。 ヒープ化後、次のヒープが生成されます。

Heapify