heap - 如何删除最大堆中的最小键？

Question

我需要实现一个函数 HEAP-DELETE-MIN(Array) 来删除最大堆中的最低整数。我不是要功能本身，但是有人可以提供一些伪代码 来帮助我开始吗？这将是一个很大的帮助。该数组应在函数结束时保持最大堆。

Answer 1

本质上，您需要做的是搜索存储在数组中的隐式堆的所有叶节点。它将成为堆的叶节点，因为它的父节点必须大于它(最大堆属性)，并且我们知道叶节点存储在索引 n/2 及以后(尽管这不会影响我们的算法复杂性)。所以基本上你应该做的是:

1) Search the array for the minimum element
2) Place the last-inserted heap element in the position of the minimum element (essentially this is the delete)
3) Upheap the replaced node to restore maximum heap property and correct storage of the heap in the array

搜索最小元素的时间复杂度为 O(n)，切换的时间复杂度为 O(1)，上堆的时间复杂度为 O(log n)。总的来说，这是线性时间，基本上是您能做的最好的。

记住要小心索引操作，2*i 是节点 i 的左子节点，2*i+1 是基于数组的堆中节点 i 的右子节点(假设数组的第 0 个元素总是空并且堆的根在索引 1)