- 一、什么是优先级队列(堆)
- 二、基于二叉树的堆(二叉堆)
- 1.二叉堆的特点:
- 2. 最大堆的实现
- 向堆中添加元素
- 在堆中取出最大值(最大堆)
- heapify——堆化
- 三、基于堆的优先级队列
- 1.通过堆实现优先级队列
- 2.优先级队列的应用——TopK问题
- 设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可
- 前k个高频元素
- 四、原地堆排序
普通队列:按照元素的入队顺序出队,先入先出。
优先级队列:按照优先级的大小动态出队(动态指的是元素个数动态变化,而非固定)。
现实生活中的优先级队列:
医生根据病人病情的情况对手术排期
病情相同的情况下按来的先后顺序,若病情较重优先安排手术
操作系统的任务调度
优先级队列,系统的任务一般优先级都比普通应用高
优先级队列的数据是在动态变化的。
时间复杂度对比:
| 入队 | 出队 | |
|---|---|---|
| 普通的链式队列 | O(1) | O(n) |
| 优先级队列 | O(log n) | O(log n) |
二、基于二叉树的堆(二叉堆)在计算机领域,若见到log n时间复杂度,近乎一定和“树”结构有关
堆有很多种(d叉堆、索引堆…),二叉堆是应用最广泛的堆。
1.二叉堆的特点:-
是一棵完全二叉树,基于数组存储(元素都是靠左排列,数组中存储不会浪费空间)
只有完全二叉树适合使用数组这种结构来存储。其他二叉树都要用链式结构。
-
关于节点值:
堆中根节点值 >= 子树节点中的值(最大堆、大根堆)
堆中根节点值 <= 子树节点中的值(最小堆、小根堆)
JDK中的PriorityQueue默认是给予最小堆的实现
①.完全二叉树
②.所有子树都满足
根 >= 子树 最大堆
根 <= 子树 最大堆
-
关于节点的编号:
因为堆是基于数组来存储的,节点之间的关系通过数组下标来表示,从0开始编号,数组下标也是从0开始
假设此时节点编号为i,且存在父节点
父节点编号 parent = (i - 1) / 2;
左子树编号 left = 2 * i + 1;
右子树编号 right = 2 * i + 2;
2. 最大堆的实现 向堆中添加元素-
数组添加元素尾插,在数组末尾添加元素——>此时仍是一棵完全二叉树,节点紧密排列;
-
添加元素后,可能会破坏最大堆的定义,因此进行元素上浮操作siftUp,直到把当前元素上浮到合适位置。
private void siftUp(int k) { while (k > 0 && elementData.get(k) > elementData.get(parent(k))) { swap(k , parent(k)); k = parent(k); } }
-
当前最大堆的最大值就在树根节点,直接取出就可;
-
将堆中最后一个元素顶到堆顶(覆盖掉最大节点),然后进行元素下沉操作siftDown使其仍满足最大堆性质。
private void siftDown(int k) { //还存在子树 while (leftChid(k) < size){ int j = leftChid(k); //此时还存在右子树 if (j + 1 < size && elementData.get(j + 1) > elementData.get(j)) { //此时右子树的值大于左子树 j ++; } //此时j一定对应了左右子树最大值索引 if (elementData.get(k) >= elementData.get(j)) { //当前元素大于左右子树最大值,下沉结束,元素k落在了最终位置 break; }else { swap(k,j); k = j; } } }
任意一个整形数组都可以看做一个完全二叉树,只需要进行元素调整操作。
方法:
-
将这n个元素依次调用add方法添加到一个新的最大堆中
时间复杂度:O(n logn )
空间复杂度:O(n)
-
原地堆化 ——> O(n)级别时间复杂度
从最后一个非叶子节点开始进行元素siftDown操作。从当前二叉树中最后一个小子树开始调整,不断向前,直到调整到根节点
public MaxHeap(int[] arr) { elementData = new ArrayList<>(arr.length); //1.先将所有元素复制到data数组中 for (int i : arr) { elementData.add(i); size ++; } //2.从最后一个非叶子节点开始进行siftDown操作 for (int i = parent(size - 1); i >= 0; i--) { siftDown(i); } }
import seqlist.queue.Queue; public class PriorityQueue implements Queue2.优先级队列的应用——TopK问题{ private MaxHeap heap; public PriorityQueue() { heap = new MaxHeap(); } @Override public void offer(Integer val) { heap.add(val); } //所谓优先级就是最大值 @Override public Integer poll() { return heap.extractMax(); } @Override public Integer peek() { return heap.peekMax(); } @Override public boolean isEmpty() { return heap.isEmpty(); } }
所有TopK问题都可以用优先级队列解决,取大用小,取小用大。
若需要取出前k个最大元素,构造最小堆
若需要取出前k个最小元素,构造最大堆
设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可示例:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tePseYbu-1654996272537)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20220609185249128.png)]
取出前4个最小元素——>构造一个大小为4的最大堆
-
若此时队列的元素个数
-
若此时元素个数 == k
- 若扫描到的元素val > 堆顶元素,一定大于此时堆中的所有元素,则val一定不是需要的结果!!直接跳过
- 若此时val<堆顶元素,将新元素val添加到队列中
- 重复以上过程,直到整个集合被我们扫描完毕,队列中恰好就保存了前k个最小值
这种方法时间复杂度为O(n logk),当k<< 需要注意的是,JDK默认是一个最小堆,需要改造成一个最大堆。 给定一个整数数组nums和一个整数 k ,返回其中出现频率前 k 高的元素。可以按任意顺序返回答案。 给定一个任意数组,在这个数组的基础上进行堆排序,不创建任何额外空间 任意数组其实就可以看做一个完全二叉树,就是将这个数组调整为最大堆。 heapify——>从最后一个非叶子节点开始进行siftDown,将数组调整为最大堆 不断交换堆顶元素和最后一个元素的位置(最大值放在最终位置),将堆顶元素继续进行siftDown 直到数组剩下最后一个未排序的元素为止class IntegerReverse implements Comparator
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Num17_14_SmallestK {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if (arr.length == 0 || k == 0) {
return ret;
}
//JDK默认是一个最小堆,需要改造成一个最大堆
Queue
前k个高频元素
import java.util.*;
public class Num347_TopKFrequent {
public int[] topKFrequent(int[] nums, int k) {
int[] ret = new int[k];
// 1.先扫描原数组,将出现的元素以及其频次保存到Map集合中。
Map
四、原地堆排序
public static void heapSort(int[] arr) {
//1.将数组调整为最大堆
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
siftDown(arr , i , arr.length);
}
//2.不断交换堆顶元素到末尾,每交换一个元素就有一个元素落在了最终位置
for (int i = arr.length - 1; i > 0; i--) {
swap(arr,0,i);
siftDown(arr,0,i);
}
}
private static void siftDown(int[] arr, int i, int length) {
while (2 * i + 1 < length){
int j = 2 * i + 1;
if (j + 1 < length && arr[j + 1] > arr[j]) {
j = j + 1;
}
if (arr[i] > arr[j]) {
break;
}else {
swap(arr,i,j);
i = j;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}



