[刷题技巧] 堆的相关知识点汇总

1. 堆

一、堆的引入

现在我们想专门设计一种数据结构，用来存放整数，要求提供3个接口：

• 添加元素
• 获取最大值(或最小值)
• 删除最大值(或最小值)

有一种最优的数据结构就是堆。
时间复杂度：获取最大值的：O(1)、删除最大值O(log n)、添加元素O(log n)

二、堆的相关概念

堆(Heap是一种树状的数据结构)，我们只学习二叉堆(也叫完全二叉堆)，堆实际就是在完全二叉树的基础上进行了一些调整，堆结构就是用数组实现的完全二叉树结构。

堆的一个重要性质：任意节点的值总是>=(或<=)子节点的值：

• 如果任意节点的值总是大于等于子节点的值，称为最大堆、大根堆、大顶堆。
• 如果任意节点的值总是小于等于子节点的值，称为最小堆、小根堆、小顶堆。

1. 堆必须是完全二叉树
2. 每一棵树的根节点必须小于/大于左右孩子结点
3. 在堆中并不意味着，上一层节点的值一定大于下一层节点的值
4. 最大堆的最大值肯定在根节点处，最小堆的最小值也是在根节点处
5. 堆中的元素必须具备可比较性

三、二叉堆

• 二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆。
• 鉴于完全二叉树的一些特性，二叉堆的底层(物理结构)一般用数组实现即可。
• 索引 i 的规律(n是节点数量)：
  • 如果 i = 0，它是根节点
  • 如果 i > 0，它的父节点的索引为 floor((i - 1) / 2)
  • 如果 2 × i + 1 <= n - 1，它的左子节点的索引为 2 × i + 1
  • 如果 2 × i + 1 > n - 1，它无左子节点
  • 如果 2 × i + 2 <= n - 1，它的右子节点的索引为 2 × i + 2
  • 如果 2 × i + 2 > n - 1，它无右子节点

因为二叉堆是用数组存储的，索引是0 ~ n-1，所以当2 × i + 1 <= n - 1时，它的左子节点存在，索引位2 × i + 1。

四、大根堆——插入操作

流程：

• 循环执行以下操作(图中的80简称为node节点)：
  • 如果node节点 > 父节点：node节点与父节点交换位置
  • 如果node节点 <= 父节点，或者node节点没有父节点(已到达根节点)：退出循环

这个过程叫做上溢(上滤)，时间复杂度：O(logn)。

private void heapInsert(int[] arr, int index) {
	// 当前元素arr[index],当前元素的父结点arr[(index - 1) / 2]
	// 退出会有两种情况:arr[index]不必arr[父]大了、index来到了树的根节点位置
	while (arr[index] > arr[(index - 1) / 2]) {
		swap(arr, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

交换位置的优化。

private void siftUp(int index) {
	E element = elements[index];
	while (index > 0) {
		int parentIndex = (index - 1) >> 1;
		E parent = elements[parentIndex];
		if (compare(parent, element) >= 0) break;
		elements[index] = parent;
		index = parentIndex;
 	}
	elements[index] = element;
}

五、大根堆——删除操作

流程：

1. 用最后一个节点覆盖根节点
2. 删除最后一个节点(也就是删除堆顶元素)
3. 循环执行以下操作(图中的43简称为node节点)
   1. 如果node节点 < 子节点：与最大的子节点交换位置
   2. 如果node节点 >= 子节点，或者node没有子节点：退出循环

这个过程叫做下滤(Sift Down)，时间复杂度：O(logn)
同样的，交换过程也可以像删除过程一样进行优化。

// 从index位置，往下看，不断地下沉
// 停：我的孩子都不再比我大；已经没有孩子了
private void shifDown(int[] arr, int index. int heapSize) {
	int left = index * 2 + 1;
	while (left < heapSize) {
		// 左右两个孩子中,谁大，谁把自己的下标给largest
		// 右孩子大--> 1)有右孩子 2)右孩子的值比左孩子大
		// 否则都是左孩子大
		int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
		// 最大值与index(父节点)进行比较
		largest = arr[largest] > arr[index] ? largest : index;
		if (largest == index) break;
		swap(arr, largest, index);
		index = largest;
		left = index * 2 + 1;
	}
} 

六、最大堆——批量建堆(heapify)

• 批量建堆，有2种做法：
  • 自上而下的上滤
  • 自下而上的下滤(效率比较高)

自上而下的下滤

// 根节点不用上滤,所以索引从1开始即可
for (int i = 1; i < size; i ++) {
	siftUp(i);
}

自下而上的下滤

// 从最后一个非叶子节点开始
for (int i = (size >> 1) - 1; i >= 0; i --) {
	siftDown(i);
}

效率对比

七、优先队列(Priority Queue)

• 普通的队列是FIFO原则，也就是先进先出
• 优先级队列是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队
• 根据优先队列的特点，很容易想到：可以直接利用二叉堆作为优先队列的底层实现
• 可以通过Comparator 或 Comparable去自定义优先级高低

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构

public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构

public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null

public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器

八、LeetCode相关题目

Top-K问题：

• LeetCode23. 合并K个升序链表
• LeetCode215. 数组中的第K个最大元素
• LeetCode347. 前K个高频元素
• LeetCode703. 数据流中的第K大元素
• LeetCode451. 根据字符出现频率排序
• LeetCode378. 有序矩阵中第K小的元素
• LeetCode692. 前K个高频单词
• LeetCode373. 查找和最小的K对数字

2. 比较器

堆中的元素必须具备可比较性，元素是通过比较大小来排序的。所以PriorityQueue的底层必定有比较大小的东西。

内部比较器——Comparable.compareTo(E o)

Comparable是JDK提供的泛型接口类。源码如下：

public interface Comparable<E> {
    // 返回值:
    // < 0: 表示 this 指向的对象小于形参 o 指向的对象
    // == 0: 表示 this 指向的对象等于形参 o 指向的对象
    // > 0: 表示 this 指向的对象大于形参 o 指向的对象
    int compareTo(E o);
}

该方法可以比较出数据的大小，所以我们可以在定义类的时候实现Comparable接口重写里面的compareTo方法

1. Comparable 接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序。
2. 实现 Comparable 的类必须实现 compareTo (Object obj）方法，两个对象即通过 compareTo (Object obj）方法的返回值来比较大小。如果当前对象 this 大于形参对象 obj ，则返回正整数，如果当前对象 this 小于形参对象 obj ，则返回负整数，如果当前对象 this 等于形参对象 obj ，则返回零。
3. 实现 Comparable 接口的对象数组可以通过 Collections.sort 或Arrays.sort 进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

注：像 String 、包装类等实现了 Comparable 接口，重写了 compareTo(obj) 方法，进行了从小到大的排

外部比较器——Comparator.compare(T o1, T o2)

public interface Comparator<T> {
// 返回值:
// < 0: 表示 o1 指向的对象小于 o2 指向的对象
// == 0: 表示 o1 指向的对象等于 o2 指向的对象
// > 0: 表示 o1 指向的对象等于 o2 指向的对象
int compare(T o1, T o2);
	
}

1. 当元素的类型没有实现 java.lang.Comparable 接口而又不方便修改代码，或者实现了 java.lang.Comparable 接口的排序规则不适合当前的操作，那么可以考虑使用 Comparator 的对象来排序，强行对多个对象进行整体排序的比较。
2. 重写 compare(Object o1,Object o2) 方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
3. 可以将 Comparator 传递给 sort 方法（如 Collections.sort 或 Arrays.sort ),从而允许在排序顺序上实现精确控制。
4. 还可以使用 Comparator 来控制某些数据结构（如有序 set 或有序映射）的顺序，或者为那些没有自然顺序的对象 colection 提供排序。

总结

PriorityQueue出队是根据优先级大小来进行出队的。
优先/不优先是取决于对比较器的定义。

3. 题型一：Top-K问题

Top-K问题解决思路

例：有一堆元素，让你找出前三个最小的元素。

• 思路一： 将数组从小到大排序，拿到数组前3个元素。但是可以发现这样时间复杂度太高，不可取。
• 思路二： 将元素全部放入一个堆结构中，然后弹出三个元素，每次弹出的元素都是当前堆最小的，那么弹出的三个元素就是前最小的三个元素。这种思路可以做，但是假设我有1000000个元素，只弹出前三个最小的元素，那么就要用到大小为1000000的堆。这么做空间复杂度太高，不建议用这种方法。
• 思路三：我们需要得到三个最小的元素，那么就建一个大小为3的堆，假设目前的堆结构中刚好放满了3个元素，那么这三个元素就是当前最小的三个元素。假设第四个元素是我们想要的元素之一，那么前三个至少有一个元素不是我们想要的，就需要弹出，那么弹出谁呢？我们要得到的是前三个最小的元素，所以当前堆结构中最大的元素一定不是我们想要的，所以这里我们建一个大根堆。弹出该元素，然后放入第四个元素，直到遍历完整个数组。

总结

1、如果求前K个最大的元素，要建一个小根堆。
2、如果求前K个最小的元素，要建一个大根堆。
3、如果求第K大的元素，要建一个小根堆 ( 堆顶元素就是 )。
4、如果求第K小的元素，要建一个大根堆 ( 堆顶元素就是 )。

相关题目

Top-K问题：

• LeetCode23. 合并K个升序链表
• LeetCode215. 数组中的第K个最大元素
• LeetCode347. 前K个高频元素
• LeetCode703. 数据流中的第K大元素
• LeetCode451. 根据字符出现频率排序
• LeetCode378. 有序矩阵中第K小的元素
• LeetCode692. 前K个高频单词
• LeetCode373. 查找和最小的K对数字(这个题有问题)

4. 题型二：中位数

相关题目

求中位数：

• LeetCode295. 数据流的中位数

本栏目推荐文章
• Maven常见问题与原理技巧
• GitHub常用搜索技巧
• UCB Data100：数据科学的原理和技巧：第十一章到第十五章
• UCB Data100：数据科学的原理和技巧：第十六章到第二十章
• UCB Data100：数据科学的原理和技巧：第一章到第五章
• UCB Data100：数据科学的原理和技巧：第六章到第十章
• 构造题技巧
• 学习方法：知识模块
• 一些Mybatis的知识点&易错点总结
• 一文带你了解Java8 Stream流处理中的收集器技巧

知识点 技巧 知识知识点 技巧 知识 队列 知识点 技巧 知识 知识点 全攻略 框架 技巧 实用技巧 技巧 知识iphone 薪火 使用技巧 知识库 缓存 知识点 注意事项 事项 技巧 基础知识postgresql技巧 基础 知识点 技巧 知识python 知识 知识点