1

我已经阅读了删除堆根元素的算法。1. 将根元素与堆的最后一个元素交换。2.然后从根元素向下heapify（下移）。

在其他几个地方，我发现它们从最后一个元素的父级向根向上堆积。（即，在此处检查 deleteTop() 函数http://www.geeksforgeeks.org/archives/14873）因此与正确的方法混淆：- （这会因情况而异还是文章本身有误？

4

4 回答 4

1

的代码deleteTop()是错误的。

当给定这个最大堆并运行时deleteTop()：

        10
     8      7
    5 4    3 2
        ||
        ||
        \/ 

        2
     8     7
    5 4   3 10
        ||
        ||
        \/ 

        7
     8     2
    5 4   3 10

结果堆是错误的，因为 2<(3 and 10)

于 2012-08-09T19:19:25.477 回答
0

我相信堆排序概念只是识别最大或最小元素并将其从堆中删除......你可以这样做，所以它是算法的不同实现。

于 2012-08-09T16:40:30.777 回答
0

在其他几个地方，我发现它们从最后一个元素的父元素向上堆积到根。（即，在此处检查 deleteTop() 函数 http://www.geeksforgeeks.org/archives/14873）

内联评论heapify()清楚地表明该实现适用于中值流问题；但是，在通用堆结构实现中，heapify()会冒泡。有关堆实现和中值流问题的详细说明，请参阅此算法讲座。

于 2012-08-09T19:12:15.867 回答
0

基本思想是首先制作最大堆。

堆只不过是对数组元素进行排序，这些元素遵循 a[i] > a[2i+1] 和 a[2i+2] 所以你从叶节点和 swap 开始，所以你向上移动。

但是在构建最大堆时，你也可以向下移动，阅读下面的答案，我之前也有疑问

给出一个测试用例，其中从算法介绍中的堆排序失败

在创建最大堆或最小堆之后，您与最后一个元素交换，因此最大元素位于其最后的排序位置。

现在因为它是一个最大堆，每个索引都遵循条件 a[i] > a[2i+1] 和 a[2i+2] 但在第 0 个位置我们不确定它是否仍然遵循条件，因为我们已从最后一个位置交换，并且第 0 位的新元素可以大于或小于其子元素。

所以如果它更小，我们交换，我们继续向下移动，直到堆属性得到满足，然后我们用 n-1 位置交换并继续。

因此，为了回答您的问题，在构建最大堆时，我们向上移动并且我们也必须向下移动，以防交换导致堆属性违规。

但是一旦我们建立了最大堆，并且我们在该过程中与最后一个元素交换，我们只会向下移动，因为除了第 0 个位置之外的每个位置都满足堆属性。

于 2020-03-18T15:23:43.010 回答