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

调用remove min函数后，我将如何“堆”化Java中基于数组的最小堆（这简单地是将索引1的元素删除，然后将其替换为数组中的最后一项）。我对删除分钟发生后如何将阵列再次放入最小堆感到困惑。

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

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

最佳答案

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

关于java - 删除min后如何“堆化”基于数组的min堆？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26671832/