chapter_sorting/heap_sort/

[giscus[bot]]

chapter_sorting/heap_sort/

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

https://www.hello-algo.com/chapter_sorting/heap_sort/

[zhuasdfg]

if (l < n && nums[l] > nums[ma])
            ma = l;
if (r < n && nums[r] > nums[ma])
            ma = r;

这里代码和堆那节siftDowm代码有点不一样，这样不能判断三个里面谁最大吧

[krahets]

Hi 是哪里不一样呢？

[zhuasdfg]

是我搞错了，代码没错，我把那几个索引弄混了

[lt421]

    for i in range(len(nums) - 1):
        nums[0], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[0]
        sift_down(nums, 0, len(nums) - 1 - i)
        print(nums)

“从堆中提取最大元素，循环 n-1 轮”我这样写对我容易理解一点

[zhuasdfg]

有时候看指针看着头有点晕，心里知道指针指向的是元素的索引，但自己去想总弄混到元素上

[krahets]

给定数组 nums ，索引 i 对应的元素为 nums[i] 。我们约定俗成地将变量 i 称为指针，意在“指向一个元素”。

[1925miles]

我觉得图片里的那个例子交换元素后进行大根堆调整的过程体现不够明显

[krahets]

我想想如何优化

[duwenba]

可不可以考虑使用manim之类的动画引擎制作GIF动画😕😕

[krahets]

@duwenba 哈哈哈 有没有类似的 demo 可以看看

[duwenba]

https://github.com/duwenba/manim_demo @krahets

[selfboot]

可以来堆可视化页面看下动画演示吧。

提供了多种堆操作的可视化演示。你可以通过界面上的切换按钮在大根堆和小根堆之间自由切换，切换时系统会自动重新构建整个堆结构。

在输入框中输入数字并点击"插入节点"按钮，可以观察新节点如何通过上浮（heapify up）操作找到其正确位置。

当点击"删除根节点"按钮时，你将看到堆顶元素被移除，以及最后一个节点如何通过下沉（heapify down）操作重建堆的平衡。删除的节点会在右侧短暂显示，随后会消失。

此外，页面还提供了随机初始化功能，可以快速生成一个包含10到50个随机数值的新堆，方便进行各种测试和观察。

[Yiiip]

    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }

获取最后一个非叶子节点的索引，友情提示 nums.length / 2 - 1 等价于 (nums.length-1 - 1)/2

[csj-9-9]

👍最后一个非叶子节点就是最后一个节点的父节点

[chaojiwudidashuaige492]

public static void heapSort(int[] nums){
   //初始化堆
   for(int i= nums.length/2-1;i>=0;i--){//((nums.length-1)-1)/2
      siftDown(nums, nums.length, i);
   }
   for(int i= nums.length;i>0;i--){//有效长度(迭代有效长度)
      swap(nums,0,i-1);//首和有效区间的尾交换，即0和有效长度-1
      siftDown(nums,i-1,0);//向下堆化，此时有效长度已经-1了，因为已经“出去一个”
   }
}

直接从nums.length-1开始逆序遍历有点不好理解，虽然结果对了

[chaojiwudidashuaige492]

i>1

[akfc58]

从下向上堆化，时间复杂度会低 (O(n))。

[akfc58]

            if (l < n && nums[ma] < nums[l]) {
                ma = l;
            }
            if (r < n && nums[ma] < nums[r]) {
                ma = r;
            }

作者好，
siftdown()当中这一段不太理解：节点i应该跟l、r中较大的交换。根据这段代码，如果l、r都比i大，则一定会与r交换（第二个if）。这样没有问题吗？

[akfc58]

打完字以后看懂了，ma一开始指向i，只在出现更大值的时候指向新的值，这样i、l、r过一遍，ma一定指向的是最大值。

[tstanon]

堆排序（从大到小，C语言版本）

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 heaptifyDown(float *arr, int size, int idx) { // 比较当前节点与其左右子节点的大小。选择最小的子节点，如果当前节点大于这个子节点，则交换它们，并继续向下调整。
    int cur = idx;
    while (true) {
        int lc, rc, minidx = cur; getLeftChild(cur, &lc); getRightChild(cur, &rc);
        if (lc < size && arr[lc] < arr[minidx]) { minidx = lc; } // 找到当前节点和左子节点中的最小值
        if (rc < size && arr[rc] < arr[minidx]) { minidx = rc; } // 找到当前节点和右子节点中的最小值
        if (minidx == cur) break; // 如果当前节点是最小值，退出循环
        float tmp = arr[cur]; arr[cur] = arr[minidx]; arr[minidx] = tmp; cur = minidx;  // 交换当前节点和最小值节点, 更新 cur 为新的索引
    }
}
void freeHeap(float **arr) { if (*arr) { free(*arr); *arr = NULL; } }
void buildHeap(float *arr, int size){
    // 使用heaptifyDown的原因是，如果使用 heaptifyUp从树的底部向上调整，每个节点在最坏情况下可能需要一直移到树的根部(并且底部的节点数量多)。
    // 这意味着可能需要执行更多的比较和交换操作。而如果我们从上往下调整，每个节点最多只需要向下移动几层（通常是树的高度），这使得整体效率非常高。
    for (int i = size / 2 - 1; i >= 0; i--) heaptifyDown(arr, size, i); // 从最后一个非叶子节点（size/2 - 1）开始，向上调整堆;
}
void heap_sort(float *heap, int size){ // 堆排序，从大道小排序
    buildHeap( heap, size); // 构建小顶堆
    while (size > 1) {
        float tmp = heap[0]; heap[0] = heap[size - 1]; heap[size - 1] = tmp; size--; // 将堆顶元素与堆的最后一个元素交换，每次循环最小的元素被调整到末尾，堆的大小减1
        heaptifyDown(heap, size, 0); // 从堆顶开始重新调整堆
    }
    freeHeap(&heap);
}

[tstanon]

freeHeap代码仅限于堆内存释放，如果是静态数组，则不适用。

[1595690293]

K神，文中代码注释提到【# 建堆操作：堆化除叶节点以外的其他所有节点】。为什么不堆化所有节点呢？

[pianfan]

因为没必要堆化叶节点，叶节点没有子节点

[Harris-peng]

堆化时会对比当前节点、左子节点、右子节点，取最大值，首次对比时左右子节点为叶子结点，已经参与对比了，所以无需堆化叶子节点

[selfboot]

看到有人评论说还是不太理解这个过程，刚好我这里有个堆的可视化演示，可以直观看到过程

[zhuiguang49]

感觉很棒！如果能自己单步往下就好了

[Cocopie-ye]

请问手动实现需要掌握吗，还是会用java内置的priority queue就行了