如何删除最大堆中的最小密钥？

Question

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

Answer 1

基本上你需要做的是搜索存储在数组中的隐式堆的所有叶节点。它将是堆的叶节点，因为它的父节点必须大于它（max heap属性），并且我们知道树叶是从索引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）的对upheap。总的来说，这是线性时间，基本上你可以做的最好。

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