一旦调用了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 - 删除最小值后如何基于 "heapify"数组的最小堆?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26671832/