java - 最小値を削除した後、配列ベースの最小ヒープを「ヒープ化」する方法は?

Question

remove min 関数が呼び出されたら、Java で配列ベースの最小ヒープをどのように「ヒープ化」しますか (これは単にインデックス 1 の要素を取得して削除し、配列の最後の項目に置き換えます)。remove min が発生した後、配列を最小ヒープに戻す方法について混乱しています。

ヒープ最小配列では、インデックス 0 は常に空のままです。親インデックスは i/2、右の子は 2i + 1、左の子は 2i です。

どんな助けでも大歓迎です、ありがとう！

Answer 1

最後の要素を取得して最初の位置にコピーします。ヒープサイズを 1 減らしheapify()て、最初の要素を呼び出します。ヒープは自動的に修復されます。これは O(log n) の複雑さを持っています

Min-Heapify-Down (Array A, int i):
    left ← 2i
    right ← 2i + 1
    smallest ← i

    if left ≤ heap_length[A] and A[left] < A[smallest] then:
        smallest ← left
    if right ≤ heap_length[A] and A[right] < A[smallest] then:
        smallest ← right

    if smallest ≠ i then:
        swap A[i] ↔ A[smallest]
        Min-Heapify-Down(A, smallest)