chapter_heap/heap/

[giscus[bot]]

chapter_heap/heap/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_heap/heap/

[hello-ikun]

这部分的py我先预定一下。今晚回去更一下

[krahets]

好，冲！

[neonhanako]

"输入数据并建堆"小节中提到“元素入堆的时间复杂度为O(n)”，这里应该是O(logn)吧，“元素入堆”那一小节也提到了这一点（ps.很感谢k神的教程，一路看下来帮助很大（刚刚回复到别人的评论上了不好意思orz

[krahets]

原文是正确的～

• 元素入堆是对单个元素的操作，时间复杂度是 $O(\log n)$ ；
• 建堆是一次性输入 $n$ 个元素，如果用元素入堆来实现是 $O(n \log n)$ ，但可以被优化到 $O(n)$ ；

谢谢鼓励哇，一起加油

[Github-632]

歪个楼，想请问下堆顶元素出堆的poll（）用的是单词的哪个含义呀，有无英语好的大佬解答一下呢。是poll的头顶，顶部；还是轮询，查询

[Github-632]

poll还有“截掉（动物，尤指小牛）的角“的意思，感觉这个最形象！

[krahets]

Hi，这里沿用了 Java 中的 poll() ，与之对应的操作是 offer() ～

[PPcattt]

heap.java 堆顶元素出堆好像没有名为heap的堆

[PPcattt]

说的是采用数组存储堆，而实际确实使用列表来实现堆

[krahets]

emmm 这里我们没有特意区分动态数组和数组。使用动态数组是为了方便扩容。

[fallenleavesguy]

请问一下，堆排序怎么样的，能不能补充一下呢。二叉搜索树排序能明白，但是堆 “依次将所有元素弹出”也不是有序的啊，只是上面的比下面的大，下面的还是保证不了顺序的。能简单说一下吗？谢谢大佬

[krahets]

哈喽，这里的“弹出”是指元素出堆。每次出堆时，堆都会进行相应调整，保持根节点最小（或最大）。

堆排序会加在排序算法章。

[fallenleavesguy]

请问一下，这里的“堆”与程序语言中的在堆中为对象分配内存，是同一个东西吗？

[krahets]

好问题～两者不是同一个东西，只是碰巧都叫"堆"。

计算机系统内存中的"堆"是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄露。相较于栈内存，堆内存的管理和使用需要更谨慎，不恰当的使用可能会导致内存泄露和野指针等问题。

[mech-jiangyuxu]

k神，堆初始化的时候，这一段代码没搞明白，
def init(self, nums: list[int]):
self.max_heap = nums
for i in range(self.parent(self.size() - 1), -1, -1):
self.sift_down(i)
我理解为直接从堆顶往堆底比较就可以了，为啥不是以下这种方式呢？
def init(self, nums: list[int]):
self.max_heap = nums
self.sift_down(0)

[mech-jiangyuxu]

这个排版怎么自己乱了。

[krahets]

这里是建堆操作，下一节有讲哦

[zhuasdfg]

k神，代码里的注释能不能写的更详细一点，特别是这几节我每次看代码都要理解好久，// 当“越过根节点”或“节点无需修复”时，结束堆化if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))，就像这里p<0，我想了好一会才理解它是根据parent()表示的越过根节点。

[krahets]

好的，不过写太详细代码也会变冗长。每当遇到“想很久才明白”的情况，往往也是变强的时刻

[cylovecode]

siftUp(size() - 1); k神，这里的size(),不用写成maxHeap.size()吗？

[cylovecode]

int size = maxHeap.size(); 不好意思没有看到前面的定义，不过我有点疑惑这个为啥定义了用的时候还要带个括号

[krahets]

请区分变量和方法，size() 是调用方法，size 是访问变量

[luommy]

不错，感觉可以和cookbook一起看，labuladong的感觉不适合算法新手完全看不进去

[malone6]

哪个cookbook？

[luommy]

halfrost，go版本的那个

[sdz123]

堆顶元素出堆 为什么选择操作交换堆顶和最右子节点而不是交换堆顶和最底层最左子节点呢？

[krahets]

在二叉树的数组表示中，最右下角的子节点对应数组的最后一个元素，这样弹出操作是安全的。

如果和最左下角的元素交换，然后将交换后的最左下角的元素弹出，则该元素后面的元素都会发生“位移”，相当于将二叉树部分的底层节点左移了。这样有可能会破坏堆的性质，是有问题的。

[sdz123]

感谢您的回复，豁然开朗。

[Tinywan]

为何没有PHP?

[krahets]

因为你没有来贡献 🤣

[2000cris7]

哈哈哈哈哈

[KLM1109]

my_heap.cpp多了行注释// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出

[krahets]

谢谢！

[topul]

不错，跟《Java编程的逻辑》一起看，看看Java的实现，看看大佬的实现，加强印象

[nlsxsy]

元素入堆那里，高度为什么要加上时间复杂度啊

[fishmans06]

您这回复效率，实在令人佩服……

[2000cris7]

哈哈哈哈

[namekkozZ]

“从顶至底堆化”的操作方向与“从底至顶堆化”相反，我们将根节点的值与其两个子节点的值进行比较，将最大的子节点与根节点交换
这里不是很理解根节点要跟最大的子节点进行交换 另一个节点交换会有什么问题吗

[krahets]

跟另一个节点交换，交换后的根节点仍然不是最大的，堆化操作无效了（不符合大顶堆的定义）

[wbzyo]

这里是大顶堆的操作，大顶堆的定义是任意节点的值>=其子节点的值

[raikiriww]

8.1.3 堆的常见应用中优先队列部分的“而建队操作为O(n)”是不是拼错了，应该是“建堆”吧？

[krahets]

在这里都行，可以理解为“建优先队列操作”

[480284856]

这个操作是基于一串数据，构建一个堆吗？那这个操作应该是n个入堆操作吧？这不应该是O(n log n)吗？

[krahets]

@480284856 看完下一节你就明白了

[wtw00928]

maxHeap.add(val)不是已经确保了堆的正确性了嘛，为什么还要siftUp(size() - 1)？

[curly210102]

my_heap.java 是基于 ArrayList 实现一个堆
https://github.com/krahets/hello-algo/blob/main/codes/java/chapter_heap/my_heap.java

[a2635814919]

add操作只是把val加入到存储空间的尾部，不能确定位置是否正确，所以通过向上堆化的方式确保堆的性质成立

[weijiaduo]

从理论上说，堆不是一棵完全二叉树，而是基于数组实现的堆才是一棵完全二叉树。如果基于指针实现的堆，不一定是完全二叉树。堆的定义中只要求父子节点保证有序性，并没有说一定是完全二叉树。

[krahets]

Hi，谢谢指出！本文中的“堆”特指“Binary Heap”，后者是前者最常见的实现方式。由于极少使用其他实现方式，因此我们一般在讨论堆时，会将两者视为同一概念。

https://en.wikipedia.org/wiki/Binary_heap
a binary heap is a complete binary tree;

我在文中说明一下两者的的关系

[Autumn00air]

note:
入堆是sift up
出堆是sift down
方向是看新改变的元素可能显得突兀的地方
至于中间元素的添加和删除呢？不好意思，只能访问和删除堆顶
sift down的时候要选个最大的，是因为有两个子节点，sift down的时候只有一个父节点

[WalkerInAI]

Python
文件heap.py中flag定义了两次：
flag = 1
...
flag = -1
这样会使 = 1的情况无法使用，或许用min_heap，max_heap阅读起来会更清晰

[WalkerInAI]

min_heap = 1
max_heap = -1

[wbzyo]

或者min_flag = 1，max_flag = -1

[wxnzb]

maxHeap->size - 1。为啥要-1

[a2635814919]

因为是存储在数组里面的，数组是从下标0开始存储，不是1，maxHeap->size返回的是堆存储空间（数组）的大小，不是最后一个元素的下标

[wxnzb]

// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
if (max == i) {
break;索引lr越界，这是怎么判断的？

[a2635814919]

在前两步的判断中，l与r如果不合法是不会与max进行交换的，即 i 的值不变 ➡ i == max

[a2635814919]

        if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[max]) {
            max = l;
        }
        if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[max]) {
            max = r;
        }

[superFlyMoose]

作者你好，我觉得在删除节点之前将size进行递减操作比较好，因为当堆剩下一个元素时，会出现数组越界的错误

int pop() {
    // 判空处理
    if (isEmpty())
        throw new IndexOutOfBoundsException();
    // 交换根节点与最右叶节点（交换首元素与尾元素）
    swap(0, size() - 1);
    size--;//提前更新
    // 删除节点
    int val = maxHeap.remove(size() - 1);
    // 从顶至底堆化
    siftDown(0);
    // 返回堆顶元素
    return val;
}

[superFlyMoose]

删除节点那里的remove参数改成size()

[superFlyMoose]

哦不，没事了，没有看到size()是直接返回列表的size()方法😂

[haerker]

k神，提个小问题，8.1.2第一句，>=的取逆好像是<

[krahets]

谢谢，这里确实有歧义，幸好括号里做了说明。我想想怎么改

[wqc18737346950]

作者你好，我有个问题比较好奇，就是堆顶出堆操作既然需要用到自顶向下的堆化操作，那为什么入堆的时候不能直接从堆顶而是要从堆底开始呢？这样不会多写一个函数嘛？

[Kai1188]

这个和数组的存储结构有关。堆采用的是数组的顺序存储，如果从堆顶开始入堆，这个元素该放哪呢？
如果放堆顶，那么就得把所有元素都往后一格，显然得不偿失。
而把元素插在数组队尾是很容易的，接下来再维护堆就好了。

[a2635814919]

作者你好，我有个问题比较好奇，就是堆顶出堆操作既然需要用到自顶向下的堆化操作，那为什么入堆的时候不能直接从堆顶而是要从堆底开始呢？这样不会多写一个函数嘛？

直接从堆顶开始的话，要么是把堆顶元素换到末尾，将新堆顶往下堆化，要么是从堆顶往下找比他小(或大)的元素，这样逻辑上更复杂了吧？

[FahaxikiLz]

作者你好，1.堆的删除只能从堆顶删除嘛？可以删除任意一个节点嘛？2.堆顶元素出堆那一节，“交换根节点与最右叶节点”，这个最右叶子节点我为啥感觉是7的右子节点。

[Danmushu]

k神你好，我想问一下这里为什么不写成下面这个样子？是有一些别的考量吗？

/* 从节点 i 开始，从底至顶堆化 */
void siftUp(int i) {
    int p = parent(i);// 获取节点 i 的父节点
    while (p < 0 || maxHeap[i] <= maxHeap[p]) {
        // 当“越过根节点”或“节点无须修复”时，结束堆化
        // 交换两节点
        swap(maxHeap[i], maxHeap[p]);
        // 循环向上堆化
        i = p;
        p = parent(i);
    }
}

[KLYkl]

我猜你应该是想写成：while (p >= 0 && maxHeap[i] > maxHeap[p])

[Jared-lu]

siftDown()方法在交换元素后应该递归调用自身吧？不然交换元素后，子树有可能不满足堆的定义

[Jared-lu]

噢噢，是我看错了，i=max就有