文章目录
- 一、概念
- 二、堆的使用
- 三、PriorityQueue 介绍
- 3.1 PriorityQueue 的特性
- 3.2 PriorityQueue 的方法
- 3.3 集合框架中PriorityQueue的比较方式
- 四、堆的应用
一、概念
1.什么是优先级队列
队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，比如我们在处理事情的时候，会优先性处理最重要的事，在该种场景下，使用队列显然不合适，由此引出了优先级队列的概念
2.什么是堆
JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整（堆可以模拟实现优先级队列）
对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低
- 双亲节点和孩子节点的关系(i为节点在数组中的下标)
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
二、堆的使用
1.结构
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
}
2.堆的创建
堆创建的时间复杂度为O(n) ----------------->数学计算
public static void createHeap(int[] array) {
// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
}
//创建一个大根堆 时间复杂度O(N)
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//把原始数据 给到了 elem数组
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
shiftDown(parent,usedSize);
}
}
/**
*
* @param parent 每棵子树的根节点
* @param len 代表每棵子树的结束位置
*/
private void shiftDown(int parent,int len) {
int child = 2 * parent+1;
//是不是一定有左孩子
while (child < len) {
//一定 不会越界 ！！！！
if(child + 1 < len && elem[child] < elem[child+1]) {
child = child + 1;
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2 * parent+1;
}else {
//此时本身 就是一个大根堆
break;
}
}
}
3.堆的插入
- 先将元素放入到底层空间中(注意：空间不够时需要扩容)
- 将最后新插入的节点向上调整，直到满足堆的性质
public void push(int val) {
//1. 检查满
if(isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
//2、存数据
elem[usedSize] = val;
usedSize++;
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize == elem.length;
}
public void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
4.堆的删除
- 将堆顶元素对堆中最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整
public void poll() {
if(empty()) {
throw new HeapEmptyException("优先级队列是空的！");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;//9
shiftDown(0,usedSize);
}
public boolean empty() {
return usedSize == 0;
}
peek()方法
public int peek() {
if(empty()) {
throw new HeapEmptyException("优先级队列是空的！");
}
return elem[0];
}
三、PriorityQueue 介绍
Java集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的
3.1 PriorityQueue 的特性
1.注意事项
- 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
- PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常
初始化如果传入的是对象，参数要求，这个类是实现Comparable接口的
因为offer()方法中，会最终调用一个siftUpComparable() 方法，这里会有一个强转为(Comparable)的操作，如果这个自定义类没有实现Comparable接口，就无法强转，会报错
- 不能插入null对象，否则会抛出NullPointerException
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
- 插入和删除元素的时间复杂度为
- PriorityQueue底层使用了堆数据结构
- PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
3.2 PriorityQueue 的方法
1.构造方法
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
2.PriorityQueue 的扩容
在集合中，所有的扩容都要去看grow()方法
3.其他
| 函数名 | 功能介绍 |
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度O(log2 N) ，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
3.3 集合框架中PriorityQueue的比较方式
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：Comparble和Comparator两种方式。
-
Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
-
用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。
四、堆的应用
1.PriorityQueue的实现
用堆作为底层结构封装优先级队列
2.堆排序
- 建堆
升序：建大堆
降序：建小堆 - 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
把0下标最后一个下标的数值交换，然后进行向上调整，然后再把0下标和倒数第二个下标的数值交换
public static void heapSort(){
int end = usedSize - 1;
while (end > 0){
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0, end);
end--;
}
}
时间复杂度计算：
- 创建堆 O(n) O(n) 是可以省略的
- 堆排序N * logN
3.Top-k问题 最小k个数
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
第一种方法
- 排序之后取5个数字，就是最小的
第二种方法
- 建立一个小根堆
- 弹出5次数据，就能拿出最小的五个数据
缺陷：时间复杂度过高
public static int[] smallestK1(int[] array,int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int x : array) {
minHeap.offer(x);
}
//小根堆当中 已经把数组所有的元素 存储起来了 k*logn
int[] ret = new int[k];
for (int i = 0; i < k; i++) {
ret[i] = minHeap.poll();
}
return ret;
}
第三种方法
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
- 堆的大小是K
- 遍历N个元素
- 极端情况，从第K+1个元素开始，每个元素都要进行调整N*logK次
class Imp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public static int[] smallestK(int[] array,int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Imp());
for (int i = 0; i < k; i++) {
maxHeap.offer(array[i]);
}
for (int i = k; i < array.length; i++) {
//1、获取堆顶元素的值
int top = maxHeap.peek();
if(top > array[i]) {
maxHeap.poll();
maxHeap.offer(array[i]);
}
}
int[] ret = new int[k];
for (int i = 0; i < k; i++) {
ret[i] = maxHeap.poll();
}
return ret;
}
