chapter_heap/build_heap/

[giscus[bot]]

chapter_heap/build_heap/

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

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

[hakinanako]

写的好好啊
可惜我已经是大学生了(´-ι_-｀)看着这数列就头疼Orz

[shanghai-Jerry]

建堆代码里面的逻辑不符合描述中的自顶至底的堆化过程

[shanghai-Jerry]

我理解错了，确实是自顶至底的堆化，只不过是从最底端元素开始往顶依次堆化

[ZZK520]

还是不太理解，我也感觉有矛盾的地方。8.2.2自下而上构建：my_heap.js 用的方法是 siftDown，是父节点和子节点比较，应该是自上往下堆化，这和标题"自下而上构建"不是矛盾了吗?

[krahets]

@ZZK520 需要注意区分：“自下而上”地构建整棵树，每个节点是通过“从顶至底堆化”操作进行调整的。

[Focu230104]

时间复杂度的公式T(h) = 2 ^(h+1) - h,是不是少了 -2 呀？

[Focu230104]

还有大佬，“借助入堆方法实现"中 ”在依次添加元素时，堆的平均长度为 n/2“，为什么堆的平均长度为n/2呢？

[krahets]

是的，谢谢指正。

因为依次插入 n 个元素，堆的长度从 1 增加至 n ，平均为 n/2

[Focu230104]

ok，谢谢大佬

[zhuasdfg]

看着数列头疼+1，还好写的详细

[w-tomato]

个人觉得”我们先将列表所有元素原封不动添加到堆中，然后迭代地对各个节点执行“从顶至底堆化”。“这句话说的不是很清楚，我第一次学挺懵的，我觉得这样说更清晰一些：
”我们先将列表所有元素原封不动添加到堆中，然后从堆的最后一个非叶子节点开始（因为叶子节点没有子节点），依次向上遍历每个节点，对节点执行"从顶至底堆化"的操作“
虽然这样啰嗦了一些，但是我第一次看到这里真的不清楚，尤其也没有说是从后往前遍历节点，但是示例代码里却是从后往前的

[krahets]

谢谢建议！这里我拓写了一下

[DXShelley]

请问大佬， maxHeap = new ArrayList<>(nums); 这里为什么还要创建一个ArrayList呢？
直接 maxHeap = nums 可以吗？我测试过，好像也没啥问题

[krahets]

最好不要直接在输入数据上进行修改，一般会复制一份的

[DXShelley]

将列表所有元素原封不动添加到堆中，然后倒序遍历该堆，依次对每个节点执行“从顶至底堆化”。
请问大佬，这里可以使用从底至顶堆化吗？正序遍历有什么影响吗？

[krahets]

好问题！执行“从顶至底堆化”前，我们需要确保当前节点下方的左（右）子树已经完成堆化，因此需要倒序遍历。

使用从底至顶堆化实际上就对应文中的”借助入堆方法实现“。

[Gcy-Shili]

大佬大佬，那个c语言的建堆操作的代码里，for循环中int i=size-1的话不就是从最后一个叶节点开始了嘛，如果要是从最后一个非叶结点开始的话应该是int i=parent(size-1)吧，或者说还是我哪里理解错了呀

[ZZK520]

8.2.1 自上而下构建：
这句话的逻辑我没理清楚。每当一个元素入堆，堆的长度就加一，因此堆是“自上而下”地构建的。
堆的长度就加一和 "自上而下"地构建有什么逻辑关系吗?

[palp1tate]

灭每个元素入堆，从上而下构建相当于树是慢慢从上面往下长的，这个跟堆的长度慢慢增加差不多，也就是加一

[muzishuiji]

感觉是这样理解的：“由于节点是从顶到底依次被添加进二叉树的（总是先添加到堆底，最右边的叶子结点，然后再进行堆化操作），因此堆是“自上而下”地构建的。”

[drinkmooon]

一点小建议：
建堆操作可以绕开"自上而下"和"自下而上"这样的表述，尤其是自上而下构建是对每个新入堆的元素执行从底至顶操作，而自下而上构建是对无序堆内元素执行从顶至底操作 。
比如表述为：
建堆操作分为两类：

填充空堆：
填充空堆是把元素依次入堆(插入堆底，然后自底向上冒泡到正确位置)
整理无序堆：
整理无序堆是将数组视为已建好的堆，从底部遍历非叶节点，把每个非叶结点代表的子堆整理成有序的堆

[krahets]

很好的建议，我优化一下

[FdeWENh]

应该注明，堆的高度 logN 是以（2叉树以2为底数，3叉以3为底）并且向上取整的值。
作为教科书应该体谅初学者。

[krahets]

谢谢，确实～

[yuhao-1]

一看就是没看前面的时间复杂度

[Programmer-ZX]

借助入堆方法实现的时间复杂度不是应该是：$\sum_{i=1}^N \log i$

[krahets]

是的，不过通常我们会取平均值，这样就是 $O((n/2) \log (n/2)) = O(n \log n)$

[jiangcanming]

我使用“借助入堆方法”实现建堆时，发现最终得到的结果和遍历堆化并不一致，具体实现：

// 大顶堆
class MaxHeap {
private var maxHeap: [Int]

// 构造方法，根据输入列表建堆
init(nums: [Int]) {
    maxHeap = []
    for i in nums {
        push(val: i)
    }
}

// ...

}

let maxHeap = MaxHeap(nums: [1,2,3,4,5,6,7,8])
maxHeap.print()

输出结果：[8, 7, 6, 4, 3, 2, 5, 1]
遍历堆化输出结果: [8, 5, 7, 4, 1, 6, 3, 2]

从结果看两者都符合“大顶堆”，是否可以理解相同数据源，堆化结果并不是唯一的？

[krahets]

很细心的观察！没错，给定一组数据，堆的结构并不是唯一的。我们在堆（树）中选择任意一个节点，交换它的左子树和右子树，堆的性质仍然得到满足。

[Claw-some]

在复杂度分析里面“在从顶至底堆化的过程中，每个节点最多堆化到叶节点，因此最大迭代次数为二叉树高度 log n”。这里的n应该不是整个树的节点数量，而是堆化时子树的节点数。那么后面说的复杂度为O(nlog n)不准确就好理解啦。不知道我说的对不对🤣

[krahets]

对～但可以往深想一层，为什么这里不能用平均深度乘以节点数量得到 $O(n \log n)$ 呢？这是因为二叉树越到底层节点越多，所以大部分节点的迭代次数都很少。

[SoftwareEngineerPalace]

从最后一个非叶子节点一直到根结点进行类似下沉的堆化操作，时间复杂度是O(n)，非常高效

[Transparenthyf]

大佬，8.2.2 中建堆操作第二步为什么不能使用正序遍历（层序遍历），然后调用 siftUp 方法？这样根节点到当前节点中间的节点都是有效的（好像这个操作和 8.2.1 里的逻辑是一样的）

[Transparenthyf]

看完 8.2.3 懂了，倒序遍历效率更高

[Hyrmm]

大佬关于第二种建堆方式的复杂度为O(n),我可以这样理解么：
首先除去叶节点，需要遍历堆化节点数就是 (n+1)/2 个
通过倒叙层序遍历的方式，决定了每层只要 跟其左右子几点比较，求最大值交换位置
因为倒叙遍历决定了子节点形成的树已经是个合法的子堆，所以每个节点在向下堆化时只需堆化1次，所以最终的复杂度其实就是需要堆化的节点数量，也是(n+1)/2 也就是O(n),这么理解有问题嘛

[krahets]

Hi，不完全对，只有倒数第二层的节点满足“只需堆化 1 次”，更上层的节点的堆化操作次数可能大于 1 次

[a2635814919]

@Hyrmm 考虑最坏情况，将小顶堆变成大顶堆实践一下

[bnufw]

假设完全二叉树的节点数量为 n ，则叶节点数量为最多为 (n+1)/2 ？

[krahets]

是的

[HangSeven]

怎么计算的k神，不太理解

[Freshman111]

满的情况叶节点最多，设层数为i，这个时候节点数量为2^i-1，第i-1层及前面层加一起总的节点数为2^(i-1)-1
所以可以计算出第i层节点数，也就是叶节点数为2^i-1-(2^(i-1)-1)=2^(i-1)
上面说假如节点数量为n，满的情况n为2^i-1，也就是(n+1)/2=2^(i-1)=叶节点最多的情况

[Hydrocarbon2023]

从完美二叉树开始，结论成立。之后每减去两个底层节点，两个叶节点变一个。因为取整不难验证节点总数为偶数时也成立

[Myrmecos]

可以泛化到一般情况：假设有n个节点，那么最后一个有子节点的节点编号是$floor(\frac{n-2}{2})$，而最后一个节点的编号是n-1，故相减得叶节点数量是$frac{n+1}{2}$

[fankaikai]

【我们首先创建一个空堆，然后遍历列表，依次对每个元素执行“入堆操作”，即先将元素添加至堆的尾部，再对该元素执行“从底至顶”堆化。】
【每当一个元素入堆，堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的，因此堆是“自上而下”构建的。】
感觉上边这两段话是不是矛盾了，第一段是从堆尾添加元素，第二段话怎么就变成从顶到底了？不太理解

[krahets]

假设给定一个列表，每轮向列表最右端（最后）添加元素，那么这个链表就是“自左而右”构建的
把列表换成堆，把左右换成首尾（顶底），就是原文的情况

[chumingqian]

还是没有理解， 你从最右端开始 添加元素， 不应该是 ' 自右而左' 开始构建的吗， 他的发起点是从右边开始的

[chumingqian]

我想了一下 ，如果 改成 由于节点是从顶到底依次满足堆化性质的， 因此是从上而下构建的 ， 可是这样也不对， 入堆的时候， 是依次从下往上 交换节点的， 想来还是 ，从下往上 构建的。

[tron-robin]

从最右端开始添加元素，是自左而右的，其实把“从最右端”改为“从右端”，就容易理解了

[Myrmecos]

我的理解是：从左到右添加元素入列表（自上而下），每个元素被添加进列表后经历自下而上heapify的过程（heapify up）

[AdAstraAbyssoque]

设元素数量为 $n$，每个元素的入堆操作使用 $O( \log n)$时间，因此该建堆方法的时间复杂度为 $O( n\log n)$。
上述表达讲的不算特别清楚，其中的计算方法实际上不是直接相乘，而是计算和：
$O = O( \log 1+ \log 2 + ... + \log n) = O(\log (n!)) = O( n\log n) $

[andrewperry01]

一个个插入，并保证堆结构，自上而下创建堆，是威廉姆斯提出的建堆算法时间复杂度为O(n*logn)；从最后一个非叶子结点开始构建堆，不断进行堆化，自下而上创建堆，是弗洛伊德提出来的建堆算法，时间复杂度为O(n)

[illusionno]

1.借助入堆操作实现建堆："从底至顶”堆化，堆是“自上而下”构建的，建堆时间复杂度为O(nlogn)
2. 遍历堆化实现建堆: （类似堆顶元素的出堆的后续操作）是"从顶至底"堆化，堆是“自下而上”构建的，建堆时间复杂度为O(n)

[tstanon]

大顶堆的初始化、建立、插入、出堆、释放的C语言版本代码

void initHeap(float **arr, int *size) { *arr = (float *)malloc(sizeof(float) * MAX_SIZE); *size = 0; } // 初始化堆的大小为0
void peekTop(float *arr, int size, float *x) { if (size <= 0) return ; *x = arr[0]; }
void getParent(int i, int *p_idx) { *p_idx = (i - 1) / 2; }
void getLeftChild(int i, int *lc_idx) { *lc_idx = 2 * i + 1; }
void getRightChild(int i, int *rc_idx) { *rc_idx = 2 * i + 2; }
void heaptifyUp(float *arr, int idx){
    int cur = idx;
    while (cur > 0){  // 只要 cur 不是根节点
        int par; getParent(cur, &par); if (arr[cur] < arr[par]) break; // 如果当前节点小于父节点，退出循环
        float tmp = arr[cur]; arr[cur] = arr[par]; arr[par] = tmp; cur = par;  // 交换当前节点和父节点
    }
}
void heaptifyDown(float *arr, int size, int idx){
    int cur = idx;
    while (true){
        int lc, rc, maxidx = cur; getLeftChild(cur, &lc); getRightChild(cur, &rc);
        if (lc < size && arr[lc] > arr[maxidx]) { maxidx = lc;} // 找到当前节点和左子节点中的最大值
        if (rc < size && arr[rc] > arr[maxidx]) { maxidx = rc;} // 找到当前节点和右子节点中的最大值
        if (maxidx == cur) break; // 如果当前节点是最大值，退出循环
        float tmp = arr[cur]; arr[cur] = arr[maxidx]; arr[maxidx] = tmp; cur = maxidx; // 交换当前节点和最大值节点
    }
}
void pushHeap(float *arr, int *size, float x){
    if ((*size) >= MAX_SIZE) return; // 如果堆已满，直接返回
    arr[*size] = x; (*size)++; // 将新元素放在堆的最后一个位置
    heaptifyUp(arr, (*size) - 1); // 重新调整堆
}
void popHeap(float *arr, int *size, float *val){
    if ((*size) <= 0) return; // 如果堆为空，直接返回
    *val = arr[0];
    arr[0] = arr[(*size) - 1]; // 将堆的最后一个元素放在堆顶
    (*size)--;
    heaptifyDown(arr, *size,0); // 重新调整堆
}
void freeHeap(float **arr) { if (*arr) { free(*arr); *arr = NULL; } }

[tstanon]

借助入堆操作实现

[tstanon]

通过堆化遍历来建立堆的C代码：

void buildHeap(float *arr, int *heap_size,  float *x, int size){
    memcpy(arr, x, sizeof(float) * size); *heap_size = size; // 将数组x的元素复制到堆中
    for (int i = size / 2 - 1; i >= 0; i--) heaptifyDown(arr, size, i); // 从最后一个非叶子节点开始，向上调整堆
}

[tstanon]

buildHeap使用heaptifyDown的原因是，如果使用 heaptifyUp从树的底部向上调整，每个节点在最坏情况下可能需要一直移到树的根部(并且底部的节点数量多)。这意味着可能需要执行更多的比较和交换操作。而如果我们从上往下调整，每个节点最多只需要向下移动几层（通常是树的高度），这使得整体效率非常高。

[tstanon]

更新，不使用额外空间。

void buildHeap(float *arr, int size){
    // 使用heaptifyDown的原因是，如果使用 heaptifyUp从树的底部向上调整，每个节点在最坏情况下可能需要一直移到树的根部(并且底部的节点数量多)。
    // 这意味着可能需要执行更多的比较和交换操作。而如果我们从上往下调整，每个节点最多只需要向下移动几层（通常是树的高度），这使得整体效率非常高。
    for (int i = size / 2 - 1; i >= 0; i--) heaptifyDown(arr, size, i); // 从最后一个非叶子节点（size/2 - 1）开始，向上调整堆;
}