优先级队列——堆
[TOC]
一、 堆的概念
在前面我们学习过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
二、 优先级队列的模拟实现
JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
2.1 堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2.2 堆的性质
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
与二叉搜索树不同，堆的左右节点都小于根节点，而左右节点的值没有大小关系
2.3 堆的存储方式
堆是一棵完全二叉树，因此可以采用层序的规则来顺序存储
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树空间中必须要存储空节点，就会导致空间利用率比较低
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
- 如果2 i + 1 小于节点个数，则节点i的左孩子下标为2 i + 1，否则没有左孩子
- 如果2 i + 2 小于节点个数，则节点i的右孩子下标为2 i + 2，否则没有右孩子
2.4 堆的创建
- 堆的向下调整
条件：必须左右子树已经是堆了才能调整
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
观察这棵树可以发现，根节点的左右两边已经满足小根堆的性质，只需将根节点进行向下调整即可
调整过程：
- 将此二叉树的根节点设置为 parent 节点 ，
比较 parent 节点的孩子节点的值，将孩子节点中的较小的节点设置为 child 节点
- 初始状态
比较 parent 节点和 child 节点的值的大小
- 若 parent > child , 则不满足小根堆的性质，将两者进行交换。
- 若 parent < child , 满足小根堆的性质，不进行交换，调整结束。
- 每次交换后，更新child 和parent的位置， parent =child，child = 2 *parent+1;
- 代码实现：
时间复杂度： O(logN) — parent固定,child 每次 x 2
// 小根堆的向下调整(满足parent的左子树和右子树已经是堆了)
public void shiftDown(int parent,int len){
int child = 2*parent +1;
// 必须保证右左孩子
while(child < len){
// 找到左右孩子的最小值
if(child +1 < len && elem[child] > elem[child+1]){
child++;
}
if(elem[child] < elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
// 向下调整重新更新
parent =child;
child = 2 *parent+1;
}else{
break;
}
}
}针对向下调整的思路，我们可以进行建堆，将一个数组建造成堆，从倒数第一个非叶子节点开始，从后往前遍历数组，依次进行向下调整，就可以得到一个小根堆
例：将以下数组[9,5,2,7,3,6,8] 建成一个小根堆
此时根节点的左右孩子两边的树均满足小根堆的特点，只需要调整以9为根的树向下调整即可，调整过程与结果如下
最后的结果即
- 代码实现
时间复杂度：建堆的时间复杂度为 O(n) （复杂的数学计算）
public void crearHeap(){
// 最后一个节点的下标为 i = usedSize -1
// (i - 1) / 2 即为最后一个非叶子节点的下标
for(int parent = (usedSize-1-1)/2; parent >= 0;parent--){
shiftDown(parent,usedSize);
//对每一个非叶子节点进行向下调整
}
}
usedsize - 即为最后一个叶子节点的下标，((usedsize -1) - 1) / 2 即为最后一个非叶子节点的下标
- 堆的向上调整
当我们进行元素的插入时，仍要保证这个堆是一个大根堆，则需要对堆进行向上调整
将堆进行向上调整的步骤
- 将插入的元素即最后一个叶子节点设置为 child ,其父亲节点设置为parent = (child-1) /2
- 当child > parent 时 ， 不满足大根堆的性质，将父亲节点的值与叶子节点的值进行交换
- 当child <parent 时，满足条件，不需要进行调整
调整完成之后重新更新parent 和 child 的位置，即 child = parent , parent = 2 * child +1
向上调整为大根堆的代码实现如下：
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;
}
}
}- 堆中插入一个元素时，代码实现
public void offer(int val){
//如果堆为满，则对数组进行扩容
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
//将插入的元素设置为堆的最后一个元素
this.elem[usedSize] = val;
usedSize++;
//将堆中元素进行向上调整
shiftUp(usedSize-1);
}
public boolean isFull(){
return elem.length == usedSize;
}堆的删除（删除堆顶元素）
- 将堆顶元素与队中堆中最后一个节点的值进行交换
- 将堆中的元素值减少一个
- 对堆中的元素进行向下调整
代码实现如下：
public int pop(){
if(isEmpty()){
return -1;
}
int tmp = elem[0];
elem[0] = elem[usedSize -1];
elem[usedSize -1] = tmp;
usedSize--;
//将堆中元素进行向下调整
shiftDown(0,usedSize);
return tmp;
}- 使用堆模拟实现优先级队列
public class TestHeap {
public int[] elem;
public int usedSize;
public static int DEFAULT_SIZE = 10 ;
public TestHeap() {
this.elem = new int[DEFAULT_SIZE];
}
public void init(int[] array){
for(int i = 0; i < array.length;i++){
elem[i] = array[i];
usedSize++;
}
}
// 建堆的时间复杂度为O(n)
public void crearHeap(){
// 最后一个节点的下标为 i = usedSize -1
// (i - 1) / 2 即为父亲节点的下标
for(int parent = (usedSize-1-1)/2; parent >= 0;parent--){
shiftDown(parent,usedSize);
}
}
/**
*
* @param parent 每棵子树的根节点
* @param len 每棵子树的
* 时间复杂度:O(log(n))
*/
// 小根堆的向下调整(满足parent的左子树和右子树已经是堆了)
public void shiftDown(int parent,int len){
int child = 2*parent +1;
// 必须保证右左孩子
while(child < len){
// 找到左右孩子的最小值
if(child +1 < len && elem[child] > elem[child+1]){
child++;
}
if(elem[child] < elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
// 向下调整重新更新
parent =child;
child = 2 *parent+1;
}else{
break;
}
}
}
public void offer(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[usedSize] = val;
usedSize++;
shiftUp(usedSize-1);
}
// 向上调整
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;
}
}
}
public boolean isFull(){
return elem.length == usedSize;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int pop(){
if(isEmpty()){
return -1;
}
int tmp = elem[0];
elem[0] = elem[usedSize -1];
elem[usedSize -1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public int peek(){
if(isEmpty()){
return -1;
}
return elem[0];
}
}一 、PriorityQueue
- 常用接口介绍
上文中我们介绍了优先级队列的模拟实现， Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，此处我们主要刨析和介绍PriorityQueue
关于PriorityQueue的使用要注意：
- 使用时必须导入PriorityQueue所在的包，即：
- PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常*
- 不能插入null对象，否则会抛出NullPointerException**
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
- 插入和删除元素的时间复杂度为
- PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)
- PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素、
二、PriorityQueue常用方法介绍
- 构造方法
常用的三个构造方法如下：
public class TestDemo2 {
public static void main(String args[]){
// 创建一个空的优先级队列，底层容量默认为11
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(10);
priorityQueue.offer(20);
priorityQueue.offer(12);
priorityQueue.offer(23);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
// 创建一个指定初始容量的优先级队列，容量指定位100
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(100);
// 使用ArrayList对象来创建一个优先级队列的对象（只要实现Collection接口的,都可以存入）
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(32);
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(list);
System.out.println(priorityQueue2.poll());
System.out.println(priorityQueue2.poll());
}
}注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
- 使用Student对象来创建一个优先级队列的对象
当我们在priorityQueue中存放一个Student 对象时， 可以正常放入且不发生报错。
但是当我们存放两个Studnet对象时，程序报错，出现类型不兼容异常。
public class TestDemo2 {
// 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
public static void main(String[] args) {
PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Student(10));
priorityQueue.offer(new Student(5));
}
}
前边学习抽象类和常用接口时，我们了解到Java中对于 引用数据类型的比较或者排序，一般都要用到使用 Comparable接口中的compareTo() 方法
此时我们可以实现Comparable接口，并且重写 compare()方法。
class Student implements Comparable<Student>{
public int age;
public Student(int age) {
this.age = age;
}
@Override
public int compareTo(Student o) {
return this.age - o.age;
}
}
public class TestDemo2 {
// 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
public static void main(String[] args) {
PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Student(10));
priorityQueue.offer(new Student(5));
}
}经过调试我们可以发现，此时优先级队列中的两个元素已经按照小根堆的方式调整好了。
那么PriorityQueue是怎么对其中的引用数据类型进行调整的呢？
使用this引用指向了下边的方法，并传递参数。
当queue数组初始化完毕时， 需要向数组中存放元素，即进行 priorityQueue.offer(new Student(10));
存放第二个元素时，i = 1 , size = 2 ,则需要执行 siftUp(1 , e) ,对 元素进行向上调整为小根堆 。
向下调整的过程中，使用了我们所重写的compareTo()方法，然后判断e,key对应的age的值，进行交换，如果此处不需要交换，则直接将key放入queue[1] 中即可 ， 此时，小根堆调整完成
如果想要调整为大根堆的话，只需要修改Student类中的compareTo()方法即可
class Student implements Comparable<Student>{
public int age;
public Student(int age) {
this.age = age;
}
@Override
public int compareTo(Student o) {
return o.age - this.age;
}
}
那么Integer类型的参数该如何修改为大根堆 呢？ ，Integer类型已经重写了compareTo方法，但是已经写死了，默认为小根堆的实现方式，无法修改源码，此时，我们就应该 构造Comparator 比较器来实现。
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
//return o2-o1;
return o2.compareTo(o1);
}
}
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
p.offer(4);
p.offer(3);
p.offer(2);
p.offer(1);
p.offer(5);
}
}当传入比较器时，PriorityQueue会按照 比较器的方式进行 比较，与实现Comparable 接口的方法类似，此处不再赘述，元素进而被调整为大根堆。
另一种写法 ：
public class TestPriorityQueue {
public static void main(String[] args) {
//匿名内部类，这里有一个类，实现了Comparator 这个接口，并重写了compare这个方法
PriorityQueue<Integer> p = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
}
}PriorityQueue的扩容机制：
优先级队列的扩容说明：
- 如果容量小于64时，是按照约oldCapacity的2倍方式扩容的（2*OldCapacity+2）
- 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
- Top-K问题
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
在不使用Arrays.sorrt 的情况下，使用优先级队列，（忽略时间复杂度）可以这样写：
1 . 先将数组全部放入堆中，堆会自动调整为小根堆。2 . 每次将堆顶元素弹出，堆调整之后，再继续弹出共k 个堆顶。
class Solution{
public int[] smallestK(int[] arr,int k){
PriorityQueue<Integer> pr = new PriorityQueue<>();
for(int i = 0 ;i < arr.length ;i++){
pr.offer(arr[i]);
}
int[] tmp = new int[k];
for(int i = 0 ;i < k ;i ++){
tmp[i] = pr.poll();
}
return tmp;
}
}此时的时间复杂度为 O（ｎ＋ｋlog（ｎ）），那么如何调整可以使时间复杂度进一步优化呢？
１．先将这组数据中的前Ｋ个数据建立为大根堆２. 从Ｋ＋１个元素开始，每次和堆顶元素进行比较，如果ｉ下标的元素小于堆顶元素，则进行出堆。
区别：1 . 没有整体建堆（大小为K的堆） 2. 遍历剩下n-k 个元素，每个元素与堆顶元素比较。
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] vec = new int[k];
if (k == 0) {
return vec;
}
//传入比较器，按照大根堆调整
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
//存入K个 元素
for (int i = 0; i < k; ++i) {
queue.offer(arr[i]);
}
//比较堆顶元素与剩余n - k个元素的值的大小
//如果堆顶元素较大，则弹出堆顶，重新调整，元素入堆
for (int i = k; i < arr.length; ++i) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
//将堆中元素存入数组中
for (int i = 0; i < k; ++i) {
vec[i] = queue.poll();
}
return vec;
}
}此时已经可以求出前K个最小的元素，那么第K小的元素如何去求呢？步骤基本是相似的
１．先将这组数据中的前Ｋ个数据建立为大根堆２. 从Ｋ＋１个元素开始，每次和堆顶元素进行比较，如果ｉ下标的元素小于堆顶元素，则进行出堆。
3 . 比较完成后直接弹出堆顶元素，即为第K小的元素。
