一、堆基础知识
1. 堆概念
- 堆是一种特殊的树形数据结构。根据根节点的值与子节点的值的大小关系，堆又分为最大堆和最小堆。在最大堆中，每个节点的值总是大于或等于其任意子节点的值，因此最大堆的根节点就是整个堆的最大值。在最小堆中，每个节点的值总是小于或等于其任意子节点的值，因此最小堆的根节点就是整个堆的最小值。
- 堆通常用完全二叉树实现。在完全二叉树中，除最低层之外，其他层都被节点填满，最低层尽可能从左到右插入节点。
二、堆知识扩展
1. 堆的知识
- 略。
堆题目 | 堆的应用
题目一：数据流的第k大数字
题目：请设计一个类型 KthLargest，它每次从一个数据流中读取一个数字，并得出数据流已经读取的数字中第 k（k ≥ 1）大的数字。该类型的构造函数有两个参数：一个是整数 k，另一个是包含数据流中最开始数字的整数数组 nums（假设数组nums的长度大于 k）。该类型还有一个函数 add，用来添加数据流中的新数字并返回数据流中已经读取的数字的第 k 大数字。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
题目二：出现频率最高的k个数字
题目：请找出数组中出现频率最高的 k 个数字。例如，当 k 等于 2 时，输入数组[1，2，2，1，3，1]，由于数字 1 出现了3次，数字 2 出现了 2 次，数字 3 出现了 1 次，因此出现频率最高的 2 个数字是 1 和 2。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
题目三：和最小的k个数对
题目：给定两个递增排序的整数数组，从两个数组中各取一个数字 u 和 v 组成一个数对（ u ， v ），请找出和最小的 k 个数对。例如，输入两个数组[1，5，13，21]和[2，4，9，15]，和最小的 3 个数对为（1，2）、（1，4）和（2，5）。
题目分析
难度： 略
思路： 略
参考代码
Tips：-
三、章节小结
堆又可以分成最大堆和最小堆。在最大堆中最大值总是位于堆顶，在最小堆中最小值总是位于堆顶。因此，在堆中只需要 O(1) 的时间就能得到堆中的最大值或最小值。
堆经常用来解决在数据集合中找出 k 个最大值或最小值相关的问题。通常用最大堆找出数据集合中的 k 个最小值，用最小堆找出数据集合中的 k 个最大值。
Java的库中提供了类型 PriorityQueue，虽然该类型实现了接口 Queue，但它是堆而不是队列。PriorityQueue 的构造函数能传入不同的比较规则，从而创建最大堆或最小堆。