Как «heapify» массив на основе min heap после удаления min?

Question

Как бы «heapify» минимальная куча на основе массива в java после вызова функции min min (это просто берет элемент в индексе 1 и удаляет его, а затем заменяет его последним элементом в массиве). Я смущен относительно того, как я собирался поместить массив в минимальную кучу снова после того, как произошло удаление min.

Индекс 0 всегда остается пустым в массиве минимумов кучи. Родительский индекс - i/2, правый - 2i + 1, а левый - 2i.

Любая помощь будет очень признательна, спасибо, ребята!

Answer 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)