java基本数据结构|Java基本数据结构——优先级队列（堆） java|数据结构

一、优先级队列（PriorityQueue） 1、概念队列是一种先进先出（FIFO）的数据结构，但是有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，在这种情况下使用队列就不行了，比如玩王者的时候突然女朋友一通电话，游戏屏幕瞬间被电话占领，这时候就应该优先处理电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新对象，这种数据结构就是优先级队列（PriorityQueue）。
【java基本数据结构|Java基本数据结构——优先级队列（堆）】PriorityQueue 的底层是堆，堆的底层是数组，在文章后面有详细描述
2、PriorityQueue特性 Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里主要使用PriorityQueue。
3、PriorityQueue使用的注意点

使用时必须导入 PriorityQueue 所在的包

import java.util.PriorityQueue

PriorityQueue中放置的元素必须要能够比较大小（只有实现了 Comparable 和 Comparator 接口的类才能比较大小），不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常
不能插入 null 对象，否则会抛出 NullPointerException 异常
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度均为 O(log2N)
PriorityQueue底层使用了堆数据结构

4、常用接口介绍 4.1、优先级队列的构造这里只是列举了常见的几种构造方式

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为 initialCapacity 的优先级队列。注意：initialCapacity 不能小于1，否则会抛出 IllegalArgumentException 异常
PriorityQueue(Collection c)	用一个集合来创建优先级队列

PriorityQueue当中，最小的元素就是优先级最高的元素

static void PriorityQueueDemo() {//1、创建一个空的优先级队列，默认底层容量是11 PriorityQueue queue1 = new PriorityQueue<>(); //2、创建一个空的优先级队列，底层的容量是 initialCapacity PriorityQueue queue2 = new PriorityQueue<>(50); ArrayList list = new ArrayList<>(); list.add(4); list.add(0); list.add(2); list.add(3); //3、用 ArrayList 集合来创建一个优先级队列的对象 PriorityQueue queue3 = new PriorityQueue<>(list); System.out.println(queue3.size()); System.out.println(queue3.peek()); }

运行结果：

4 1

4.2、插入/删除/获取优先级最高的元素

函数名	功能介绍
boolean offer(E e)	插入元素 e，插入成功返回 true，如果 e 对象为空，抛出 NullPointerException 异常，时间复杂度为 O(log2N) ，注意：空间不够时会自动扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回 null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回 null
int size()	获取有效元素的个数
void clean()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回 true

补充：

文章图片

5、扩容 jdk1.8 中，PriorityQueue的扩容方式：
可以在手册中搜索 grow() 函数

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { int oldCapacity = queue.length; int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2): (oldCapacity >> 1)); if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); }queue = Arrays.copyOf(queue,newCapacity); }

优先队列的扩容说明：

如果容量 < 64,按照 oldCapacity * 2 + 2 进行扩容
如果容量 >= 64，按照 oldCapacity * 1.5 进行扩容
如果容量超过 MAX_ARRAY_SIZE，按照 MAX_ARRAY_SIZE 进行扩容

6、优先级队列的应用 topK 问题 topK-LeetCode

文章图片

思路：将数组所有元素放到优先级队列当中，然后取前 K 个

class Solution { public int[] smallestK(int[] arr, int k) {int[] ret = new int[k]; if (arr == null || k <= 0) { return ret; }PriorityQueue queue = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { queue.offer(arr[i]); }for (int i = 0; i < k; i++) { ret[i] = queue.poll(); }return ret; } }

二、堆（Heap）

前提知识：二叉树的顺序存储
使用数组存储二叉树的方式，就是将二叉树按照层序遍历放入数组
一般只适合完全二叉树，因为非完全二叉树会有空间的浪费
这种方式的主要用法就是堆的表示

文章图片

已知双亲(parent)的下标
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;

已知孩子（不区分左右）(child)下标
双亲(parent)下标 = (child - 1) / 2;

1、概念概括：堆就是一颗顺序存储的完全二叉树，底层是一个数组

堆逻辑上是一颗完全二叉树
堆物理上是保存在数组中
堆满足任意结点的值都大于其子树中结点的值，也就是所有根节点 > 其左右孩子结点，叫做大堆，或者大根堆、最大堆
反之则是小堆，或者小根堆、最小堆

文章图片
堆的基本作用是快速找到集合中的最值

2、性质

堆中某个节点的值总是不大于或不小于其父结点的值
堆总是一颗完全二叉树

3、向下调整找左右孩子最大值，然后和父亲结点进行交换

代码：

public class TestHeap { public int[] elem; public int usedSize; public TestHeap() { this.elem = new int[10]; this.usedSize = 0; } /* code here */ }

/** * 向下调整 * @param root 每棵子树根节点 * @param len 每棵子树结束位置 */ public void adjustDown(int root,int len) { int parent = root; int child = 2*root + 1; while (child < len) { //1、有右孩子 -> 找到左右孩子的最大值 if (child + 1 < len && this.elem[child] < this.elem[child+1]) { child++; //保证child保存的是左右孩子的最大值 }if (this.elem[child] > this.elem[parent]) { int tmp = this.elem[child]; this.elem[child] = this.elem[parent]; this.elem[parent] = tmp; parent = child; child = 2*parent + 1; } else { break; } } }

时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度即时间复杂度为O(log(n))

4、建堆下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
具体做法就是，从最后一个非叶子结点子树开始，比较左右孩子结点，较大的孩子结点和父亲结点比较，比父亲结点大的话就进行交换，直到这棵子树已经成了一个堆

图示（以大根堆为例）：

// 建堆前 int[] array = { 1,5,3,8,7,6 }; // 建堆后 int[] array = { 8,7,6,5,1,3 };

文章图片

时间复杂度分析：

粗略估算，可以认为是在循环中执行向下调整，为 O(n * log(n))（了解），实际上是 O(n)

代码：

/** * 向下调整 * @param root 每棵子树根节点 * @param len 每棵子树结束位置 */ public void adjustDown(int root,int len) { int parent = root; int child = 2*root + 1; while (child < len) { //1、有右孩子 -> 找到左右孩子的最大值 if (child + 1 < len && this.elem[child] < this.elem[child+1]) { child++; //保证child保存的是左右孩子的最大值 }if (this.elem[child] > this.elem[parent]) { int tmp = this.elem[child]; this.elem[child] = this.elem[parent]; this.elem[parent] = tmp; parent = child; child = 2*parent + 1; } else { break; } } }/** * 建堆 * @param array 传入的数组 **/ public void creatHeap (int[] array) { for (int i = 0; i < array.length; i++) { this.elem[i] = array[i]; this.usedSize++; } //i代表每颗子树根结点 for (int i = (this.usedSize - 1 - 1) / 2; i >= 0 ; i--) { adjustDown(i,this.usedSize); } }

要将一棵树调整为大根堆或者小根堆，方法就是 : 从这棵树的最后一个子树进行向下调整，每一颗子树都要进行向下调整

时间复杂度分析：
粗略估算，可以认为是在循环中执行向下调整，为 O(n * log(n))
（了解）实际上是 O(n)

5、插入一个元素

过程（以大堆为例）：

首先按尾插方式放入数组（空间不够时需要扩容）
比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
否则，交换其和双亲位置的值，重新进行 2、3 步骤（2、3就是向上调整的过程）
直到根结点

图示

文章图片

是一个向上调整的过程
代码

/** * 向上调整 * @param child 拿到的数组最后一个位置 */ public void adjustUp(int child) { while (child > 0) { int parent = (child - 1)/ 2; if (this.elem[child] <= this.elem[parent]) { break; } int tmp = this.elem[parent]; this.elem[parent] = this.elem[child]; this.elem[child] = tmp; child = parent; } }/** * 添加一个元素（入队列） * @param val 要插入的元素 */ public void push(int val) { if (isFull()) { //扩容 this.elem = Arrays.copyOf(this.elem,2*this.elem.length); }this.elem[this.usedSize] = val; this.usedSize++; adjustUp(this.usedSize-1); } //判断堆是否满了 public boolean isFull() { return this.usedSize == this.elem.length; }

6、删除一个元素为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是

用数组的最后一个元素替换堆顶元素，usedSize–
然后从堆顶0号位置下标的元素开始，通过向下调整方式重新调整成堆

文章图片

向下调整的代码前面有写过了，可以直接用

//判断堆是否为空 public boolean isEmpty() { return this.usedSize == 0; }/** * 删除一个元素 */ public void pop() { if (isEmpty()) { throw new RuntimeException("堆为空"); }this.elem[0] = this.elem[this.usedSize-1]; this.usedSize--; adjustDown(0,this.usedSize); }

7、返回堆顶元素（优先级最高）

public int getTop() { if (isEmpty()) { throw new RuntimeException("堆为空"); }return this.elem[0]; }

三、堆排序

/** * 堆排序 */ public void heapSort() { int end = this.usedSize - 1; while (end > 0) { int tmp = this.elem[0]; this.elem[0] = this.elem[end]; this.elem[end] = tmp; adjustDown(0,end); //该方法在二.3写过了 end--; } }

四、topK问题最小k个数

//不常用 class Solution { public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if (arr == null || k <= 0) { return ret; }PriorityQueue queue = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { queue.offer(arr[i]); }for (int i = 0; i < k; i++) { ret[i] = queue.poll(); }return ret; } }

topK：有一组无序的数据，且数量庞大，求前K个最小的元素或者前K个最大的元素
比如说现在有 N 个元素，求前 K 个最小的元素

建立大小为 N 的小堆，每次弹出堆顶元素，弹 K 次（不常用）
建立大小为 K 的大堆（求前K个最大的元素建小堆）
1 ) 将待排序序列的前 K 个元素，建成大根堆
2 ) 遍历剩下的待排序序列，每拿到一个数字，就和当前堆顶元素比较
3 ) 如果比当前的堆顶元素大，不care
4 ) 如果比堆顶元素小，那么弹出堆顶元素，将待排序序列当中的数字放到堆中
第4）中的弹出和放入都对应了一次调整为大根堆的过程