堆排序(Heapsort)

[@xiaoaiwhc]

速度可以, 全是干货, 基本没有废话. 这就是效率呀. 一般的老师可以讲2个小时~~

[@haiquanzheng5224]

这是我看过中英文里讲解heap最好的视频了，讲的太全面了！！收藏点赞了👍

[@苏子涵0707]

cant agree more!

[@moonsha5851]

你的视频做得很好。 看了很多期， 学到不少东西。 感谢。

[@ymingxi]

真的讲得很好！两年前看是为了应付考试。现在看是为了应付面试。希望能继续做算法视频！

[@raetz1137]

真的講很好 質感很夠 每隔一段時間忘了又會回來複習

[@木林海风]

爱死你了黄老师，讲课声音又好听，比B站那些整天讲黄段子冷笑话的老师好多了。5分钟前对于堆排序怕的要死，现在感觉自己can control over everything.

[@G43maiwaifu]

讲黄段子和冷笑话的太真实了😅

[@jsloth0303]

都不知道什麼是好的教學視頻，直到我看到這一個。。謝謝黃老師

[@tpof314]

谢谢支持

[@taoshen7566]

板书看着真让人舒服，讲的也很好！ 持续关注！

[@mrkasa5337]

這教學真的厲害，淺顯易懂

[@coffee_milktea]

讲得好清楚啊，并且字字如金，一个字多的都没有，太赞了！

[@DickWu1111]

首先非常喜欢你的视频！ 我会把你的build_heap 叫做heapify. Python heapq 的heapify就是把整个array变成heap. 视频中的heapify 我喜欢叫成bubble down，因为是value从parent往children走。 然后视频没有cover bubble up。heappop的时候用bubble down, 如果implement heappush的话是需要bubble up的，我的理解是这样的。

[@tpof314]

可以可以。确实这样命名更容易理解一些。谢谢指正🤝

[@阿剑客]

感谢您的视频，讲的很非常清楚！😀

[@fangcai4229]

讲的很好，我自己用python实现了一遍，谢谢。会持续关注的。

[@d0805446]

实现了一遍，不讳觉得有点怕怕的吗，就是担心自己写的总是不好那种感觉？

[@jiachengyang3973]

感谢这么好的视频！希望能顺带分析一下时间复杂度和排序稳定性就好了~

[@fengyuewuhen]

清晰明了！算法小白听的很清楚，鼠标用的超帅啊

[@Convallaria_Majalis-ln4zn]

字写得好，声音好听，内容详实

[@xinwang93]

讲的真的是透彻 赞赞

[@AIxGEEK]

讲得很棒，其他老师的视频看得打瞌睡~

[@gunsnroses962]

今天终于能听懂这期的代码了谢谢你！

[@creamidea]

讲的太棒了，简直享受。

[@SoumaHsu]

講得超好~終於聽懂了，而且聲音好聽可以當ASMR哈哈哈

[@jingh1743]

請問一下 不是應該從下面比上來嗎? 如果從上面比下來 不是有可能出現根結點不是最大的情況 例如 2 7 6 10 這樣比完不是變成 7 10 6 2嗎? 謝謝 如這個影片kzbin.info/www/bejne/o5i4moxueLt3nrc&ab_channel=AbhilasBiswas

[@helloworld409]

這個太優秀了，我如沐春風！

[@JujutsuMan]

不是開玩笑...在看演算推導的書以及教授給的PPT 摸了2 3小時才似懂非懂...進來跳著看 就突然全個章節都懂了...我的天阿

[@rosawang5965]

非常清晰，感谢🙏

[@jiatongwu8808]

大佬讲的很清楚 我是做java开发的 我听明白了

[@jasonciou1906]

非常清楚的教學，感謝🙏🏻

[@汪淳羽]

感謝大兄弟的影片 之前看書完全不懂書上再寫三洨 那個 我看下面流言有提到一開始建build_TREE不用遞迴(遞歸?) 可是我是了 int[] array={5,4,3,2,1}; 從for(i=(size-1)/2;i>=0;i- -)做檢查 出來的陣列是 array1={1,5,3,2,4} 5 2 4 不是二元樹啊

[@singo1232001]

它分成 三部份 第1段 是建樹+整理一根樹枝 第2段 是建樹+整理全部樹枝 第3段 是建樹+整理全部樹枝+拆解排序

[@ItsZoeZ]

讲得太好了，感谢你制作的视频

[@huaxingwang2557]

卧槽。。。太强了，vim用的和鼠标键盘一样

[@fanfan196]

真的讲的很好 请继续讲下去 orz

[@TheRoy714]

感謝分享，受益良多!

[@Eric-wh2ex]

講的真的超級好!!!!!

[@forrestkong3455]

视频做到相当好！我照着敲都没你速度快，我的天

[@sharonjin7463]

讲得好好，画得也清楚，太棒了

[@laujimmy9282]

謝謝，講的真的很清楚

[@chaofengchen5862]

package ink.nju.api_test.临时; import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = new int[]{8,1,5,3,0,6,4,2,7,1}; heapSort(arr); System.out.println(Arrays.toString(arr)); } //节点“下沉”调整，将arr[parentIndex]放到子节点中去，因为它太小了，不能作为大顶堆的堆头 public static void downAdjust(int[] arr, int parentIndex, int len) { int temp = arr[parentIndex];//temp保存父节点值 int childIndex = 2 * parentIndex + 1;//工作指针--左孩子节点 while(childIndex = arr[childIndex]) {//父节点大于孩子节点，直接退出循环 注：这里是temp而不是arr[parentIndex] break; } arr[parentIndex] = arr[childIndex];//找到了大于父节点的子节点，将子节点赋值到父节点位置，然后修改工作指针 parentIndex = childIndex;//修改父节点指针 childIndex = 2 * parentIndex + 1;//修改工作指针 } arr[parentIndex] = temp;//将父节点的值赋值到最后parentIndex位置 } //堆排序（升序）（大顶堆） public static void heapSort(int[] arr) { //1.将无序数组构成最大堆 //这里需要理解为什么构建的是大根堆：堆本身不是有序序列，但堆头/树根总是最大或者最小的，选择大根堆，每次都能取一个最大值放最后， //然后调整堆，这样调整之后原数组就成了升序序列。这里容易混淆是因为大根堆每次取出的是最大值，很多人想当然认为是降序，其实还有将堆顶元素与未排序堆尾元素交换，并调整堆的过程，最后的结果是保存回原数组的，是原地排序。 for(int i = arr.length/2 - 1; i >= 0; i--) {//注：这里i必须要取到0 downAdjust(arr,i,arr.length); } //2.循环删除堆顶元素，调整堆产生新的堆顶 for(int i = arr.length - 1; i > 0; i--) {//这里i最小取到1 swap(arr,0,i);//每次将堆顶元素放到最后，规模越来越小，这里要理解 downAdjust(arr,0,i);//每次调整到i为止，规模越来越小，这里要理解 } } //结点交换 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

[@chaofengchen5862]

java版本，其中下沉操作是非递归版本。

[@chaofengchen5862]

参考：《漫画算法》

[@aidenliu3054]

讲得很详细，非常感谢

[@xinchen5095]

超清楚 厲害

[@ryanren3496]

大佬的视频是不是也在LeetCode里面有？声音好熟悉hhh

[@harris99716]

對i節點做heapify 的前題是 i 的左右子樹都是heap

[@judywang9859]

这个讲的很棒很清楚！

[@longchen-v5h]

非常赞，深入浅出

[@lifayan]

视频讲的很好， 是我理解错了， heapify 之后不一定是heap. 感谢！

[@tpof314]

没错的。你应该是只运行了heapify，并没有运行heap_sort

[@tpof314]

实际上是这样的：heapify的作用是把一个数组变成heap，但是heap不一定是sorted。

[@lifayan]

@@tpof314 谢谢了， 根据定义 只有 sorted 才能叫heap.

[@tpof314]

@@lifayan 不是不是。heap是堆，不是sorted array。heap只要符合"父节点大于子节点"就可以了。

[@lifayan]

@@tpof314 heap 的定义是 所有的子节点小于（或大于）父节点的平衡树。 在sort之前因为不满足这个条件，我的理解是应该不能叫heap的。 但是我明白你的意思了， heapify之后保证处理到的那个节点是heap.

[@monhanmodkhan9196]

I am impressed by the clear code, Thx!

[@l_sx8722]

I'm wondering that there is no Eng subtitle, how did u understand what he is talking about...

[@刘晨-h3m]

@@l_sx8722 我也这么think的

[@yanghaoming221]

讲的很清楚！棒棒

[@萧杰-o5e]

build_heap其实就是heapfy呀，python不用递归只需要从后面往前面i-1/2就可以build_heap

[@yingchi5200]

我想问一下这个n 是上面指的那个索引的数还是本身的数值呀

[@makechinagreatagain1679]

感觉节点的两颗子树都已经是堆，这时候堆化才有意义，不然还是乱的。

[@李M-q7e]

讲的真棒👍

[@jacobstech1777]

希望继续更新啊！

[@Shjdhhshhskshdh]

对比了pathon源码中heapify的实现，发现还是很大不同，源码的实现比你的复杂，难道源码不是最优解？谢谢

[@Penguin1014w]

讲的好好呀 搜英文的都听不懂

[@xuzhongwei9735]

请继续！

[@jacobstech1777]

可以分析一下时间复杂度

[@小命子]

谢谢老师的视频，感觉讲得很好。 是不是按照这个顺序的。 树-二叉树-完全二叉树-堆-堆排序 把一个任意的列表做完heapify之后只能说这是一个堆，并不能说是排序的。 通过算法堆排序之后才能形成一个排列好的列表。 最大堆就是从大到小排列的列表。 最小堆就是从小到大排列的列表。 是这个意思吗？

[@tpof314]

嗯，正确。heapify的结果是一个堆，还不是排序结果。

[@小命子]

@@tpof314 实在是太谢谢你了。我用的是python，然后刚才按照您的思路试着实现了一下。感觉自己对于递归还是有点不熟，感谢指点。

[@heefan-lee]

视频解析的很清楚 给cpp代码，一站到位。 最大堆， 从小到大排序， cpp void heapify(vector & arr, int n, int i) { int largest = i; int l = 2*i+1; int r = 2*i+2; if(l arr[largest]) { largest = l; } if(r arr[largest]) { largest = r; } if(largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vector & arr, int n) { for(int i=n/2-1; i>=0; i--) { heapify(arr,n, i); } for(int i=n-1; i>=0; i--) { swap(arr[0],arr[i]); heapify(arr, i, 0); } } int main() { vector array= {12,11,13,5,6,7}; heapSort(array, array.size()); return 0; }

[@HelloHello-yf8dz]

好厉害 尤其是写代码的部分 很熟练

[@ywleu8315]

大神有机会可以录一次二元堆的内容吗@_@,感觉最近的9024有点难

[@manisangyu3962]

说的太棒了

[@abouluo]

看懂了，感谢！

[@montanajony8864]

从下往上heapify可能会出现0号节点小于叶子结点的情况

[@weihu6498]

我开始跟你想的一样，后来发现heapify是个递归，就不会出现这种情况了，你再思考下，

[@arcane_x6396]

抱歉打扰。想请教一下，Heapify为什么要这样递归没有看懂，能解释一下吗？万分感谢。

[@charispsychomalin6302]

因为建堆是从下往上，heapify不递归的话不能保证先heapify的结点到最后还是堆的结构

[@rayeden1087]

请问你录制视频有用外接工具吗？还是直接用触控板/鼠标？ 好流畅啊。

[@tpof314]

Xournal我是下载后自己编译的。需要自己安装个gtk的库。

[@tpof314]

有外接的数位板。不是直接用鼠标

[@rayeden1087]

@@tpof314 是用哪款数位板？求链接··

[@tpof314]

直接在淘宝上买的。也就300多人民币，画漫画用的那种。不过，这种板子其实不太方便携带。写字其实也并没有想象中那么方便。只是比鼠标好用一点而已，要用来做笔记的话，真的不如用ipad或者surface pro

[@rayeden1087]

@@tpof314 好的 谢谢

[@anguszou3477]

谢谢老师 ：）

[@stanleychen5289]

字写的好看 好评

[@raychang4710]

謝謝老師^^

[@joshuage8542]

太棒了

[@khanhhongtranle9138]

很喜欢！谢谢你！

[@tpof314]

越南的朋友吗？还有越南的朋友看我的视频，很是荣幸～

[@khanhhongtranle9138]

是啊。 老师教的我不太懂。看你的视频后，我觉得很容易理解。你真棒！谢谢啊！

[@szhou902]

很好

[@KK-oq4zz]

妙啊

[@wxnacy9657]

请问如何在 mac 中使用 xournal

[@tinyluna4801]

同问

[@jomosis9234]

不太能领会到build heap的好处

[@tpof314]

没有build heap的话，那个数组并不能形成一个heap结构。后面的heapsort根本没办法进行。

[@jomosis9234]

@@tpof314 那么heapify(tree, n,0) 是不是和 heap_sort里的build_heap(tree, n)同等效果呢，在那里你提到build_heap可以用于处理万级数据，我不明白build_heap比直接heapify好在哪里呢（希望我没理解错）

[@tpof314]

@@jomosis9234 果然理解有误。。。heapify只能保证一个节点符合堆的性质。

[@jomosis9234]

@@tpof314 试验几次以后明白，谢谢黄老师

[@tpof314]

@張家瑞 綜高110仁18 为了保证最后的结构满足heap的性质。每一个节点都必须满足父节点大于子节点，如果不递归的话，只能保证一个点是正确的。

[@browu7838]

好強... 很清楚的知道了，不當大學講師嗎

[@clarema3469]

建堆其实不要递归，这样反而复杂吧，从(n-1)/2 往前找就行。

[@tpof314]

嗯。可以不用递归。只是由于录像时间的关系，我习惯怎么写就怎么录了。

[@张树源]

大神徒手画圆都这么○

[@tpof314]

其实～ 圆是用系统工具画的。。。徒手画圆不可能这么圆啦。。。

[@xinrutang6883]

@@tpof314 黄兄，你的课讲得很好，易懂！希望能多出一些其他的算法讲解，比如红黑树，图的Floyd算法什么的.

[@sidazhong2019]

来美国发展多好

[@薛涛-p8p]

硬啊

[@tpof314]

瑟瑟发抖

[@heefan-lee]

最小堆，从大到小排序， cpp void heapify(vector & arr, int n, int i) { int smallest = i; int l = 2*i+1; int r = 2*i+2; if(l=0; i--) { swap(arr[i], arr[0]); heapify(arr, i, 0); } } int main() { vector arr = {12,11,13,5,7,6}; heapSort(arr); return 0; }