我需要实现一个函数 HEAP-DELETE-MIN(Array) 删除最大堆中的最小整数。我不要求函数本身，但有人可以为我提供一些 伪代码来帮助我开始吗？这将是一个很大的帮助。该数组应在函数结束时保持最大堆。
问问题
4927 次
1 回答
6
本质上，您需要做的是搜索存储在数组中的隐式堆的所有叶节点。它将是堆的一个叶子节点，因为它的父节点必须大于它（最大堆属性），并且我们知道叶子是从索引 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)
于 2013-02-19T05:30:35.380 回答