java - 删除最小值后如何“堆化”基于数组的最小堆？

Question

一旦调用了 remove min 函数，我将如何在 java 中“堆化”基于数组的最小堆（这只是获取索引 1 处的元素并将其删除，然后将其替换为数组中的最后一项）。在 remove min 发生后，我对如何将数组再次放入最小堆感到困惑。

索引 0 在堆最小数组中始终保持为空。父索引为 i/2，右孩子为 2i + 1，左孩子为 2i。

任何帮助将不胜感激，谢谢大家！

Answer 1

取最后一个元素并将其复制到第一个位置。将 heapsize 减一并调用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)