堆

堆的定义：

堆是由完全二叉树实现的。

完全二叉树定义：

• 非叶子节点大于或等于（小于或等于）其左右子树的所有结点。
• 除了叶子节点，可以不满，但最后一层节点必须靠左，其余层都是满节点。

完全二叉树的分类有哪些？

大顶堆：堆顶的元素最大

小顶堆：堆顶的元素最小

分别有什么特点？

分别有什么应用场景？

可以用来排序（堆排序）。

堆的存储方式

通常使用数组存储。

数组存储堆有什么好处？

• 数组是连续的存储空间，节省空间，并且对cpu缓存有利。
• 结构紧凑。

实践：将数组转为完全二叉树；将完全二叉树转为数组；

堆有哪些常用操作？

• 插入元素
• 删除元素
• 获取最大值或最小值

分别是如何实现的？写一写常用操作的实现代码？

堆有哪些常见应用？

• 堆排序
  • 如何实现堆排序？--请跳转到排序算法章节
  • 为什么快排的性能比堆排序的性能好？--请跳转到排序算法章节
• TOP K问题
• 实现优先级队列
  • 合并有序小文件
  • 高性能定时器
• 求中位数

TOP K问题

方案：利用小顶堆。

举例：你可以需要在无序数组中找到最大的第K个元素，例如[9,3,6,1,4]，排序后为[1,3,4,6,9]，最大的第3个元素是4。此时你需要维护一个小顶堆，堆大小为K。遍历数组，往堆里添加元素，如果大于堆顶元素，则入堆，堆若满了则将最小元素出堆。数组遍历完成则堆顶元素是最大的第K个元素。

例题：

• 347.Top K Frequent Elements（前 K 个高频元素）
• 215.Kth Largest Element in an Array（数组中的第K个最大元素）