面试官：写一个堆排吧

我心想：堆排是什么鬼

理解堆排，首先要理解二叉堆。理解了二叉堆的“下沉”操作，基本上就可以理解堆排了。今天我们来看一看什么是堆，以及堆的一般操作

一、优先级队列

近日，一尘遇到了烦心事，于是找老师去诉苦了

一尘列了几个要做的事

一尘道出了心中的苦

慧能：你可以做优先级最高的事情，做完后删除它，然后做剩下优先级最高的事，当然，很有可能有其他事插入进来，新插入的事情如果优先级不是最高，就不做，这样你就一直做优先级最高的事了

接着慧能顺手画了一个图

优先级队列中每个元素都有优先级，优先级最高的最先被处理

二、优先级队列的实现

一尘非常想知道黑盒里面是什么

然后我把优先级存入一个无序数组里，取出的时候遍历数组一边，找出最小值，插入的时候直接插到集合末尾

一尘画了一幅图解释道

随后，一尘又画出了插入6后的图

三、堆

这里我们只讨论二叉堆，把二叉堆称为堆，堆也有d-堆，左式堆等等

慧能看一尘不是很明白，顺手画了个图

慧能画了一个二叉堆实例

注意：二叉堆中两个孩子之前的大小没有关系，可能左孩子>=右孩子，也可能右>=左

慧能随手画了一个小根堆和一个大根堆

本文讨论小根堆

4、插入操作

每个父节点的值小于等于其左右孩子的值被称为堆的有序性，另一种情况是大于等于也称之为堆的有序性

慧能随手画了一个插入操作破坏堆有序性的图

说完，慧能飞速地写出了上浮的代码

一尘暗自惊叹老师的代码功力

五、删除操作

一尘听完此话紧张的手心出汗，但还是硬着头皮想了想，突然灵光一现

随后一尘画出了交换后的图

一尘刚松了口气，谁知还要写代码，只见一尘想了想，写写擦擦好几遍最终写下了如下代码

如图

只见一尘又写了一段代码

leftIndex = 2*parentIndex;

rightIndex = 2*parentIndex+1;

看来以后得好好学数据结构与算法了，不然连时间都管理不好，一尘心想

另外，算法的学习也是必经之路，这里给大家推荐一个大佬的刷题笔记

帅地校招就是刷了这份笔记来应付面试官的，这里分享给大家吧。
下载链接：BAT大佬的刷题笔记太经典

把这份笔记突击学习一下，很多算法考察，基本都稳了

另外，再给大家推荐一份某大佬的 leetcode 刷题笔记，汇聚了上千道 leetcode 题解，并且代码都是 beat 100%：

下载链接：leetcode 分类题解（最优解）

就算你现在不学算法，那么这份笔记也值得你收藏，万一有人问你 Leetcode 某道题解，或者有大神在讨论题解，咱打开这份笔记，不管三七二十一，直接把最优解扔给他，然后退出群聊

额外话

堆排序的实现就是基于二叉堆的，堆排序是十大排序算法中必学的一种排序算法，这里帅地给大家找来了优质的学习文章供大家学习，网上其他文章质量参差不齐，详细经过帅地挑选的这些文章能够节省你不少时间
漫画：什么是冒泡排序算法？

漫画：什么是选择排序算法？

漫画：什么是插入排序算法？

漫画：什么是希尔排序算法？

漫画：什么是归并排序算法？

漫画：什么是快速排序算法？

漫画：什么是堆排序算法？

漫画：为什么说O(n)复杂度的基数排序没有快速排序快？

什么是计数排序算法？

十大排序算法极简汇总篇

作者简洁

作者：大家好，我是帅地，从大学、自学一路走来，深知算法，计算机基础知识的重要性，公众号「帅地玩编程」10万粉丝作者，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我一起学习，点击了解我四年大学学 习之路 转载说明：未获得授权，禁止转载

cs