【Java数据结构】--- 优先级队列

乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~
创作不易，大佬们点赞鼓励下吧~

前言

继续来看这张图，我们前面已经结束了List, Queue, 两个接口的学习。只剩下一个PriorityQueue（优先级队列）类，而为了对PriorityQueue有一个更好的理解，我们需要引入一个新概念 堆。最后希望各路大佬点点赞~

优先级队列

可能有人有这样一个疑问，前面我们有知道Queue队列，那么和这个PriorityQueue优先级队列有什么区别呢？

队列是一种先进先出的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适。

概念

像这种情况：数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。 这种数据结构就是优先级队列(Priority Queue)。

堆

JDK1.8中的PriorityQueue底层使用了堆这种数据结构。

概念

如果有一个K集合，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。
其中：满足Ki <= K2i+1 且 Ki<= K2i+2 （i = 0，1，2…）称为小根堆

           满足：Ki >= K2i+1 且 Ki >= K2i+2（i = 0，1，2…）称为大根堆

注意：
         堆中某个节点的值总是不大于或不小于其父节点的值
         堆总是一棵完全二叉树

因为堆是一颗完全二叉树，堆的逻辑存储方式与二叉树一模一样。详见：【Java数据结构】— 二叉树

创建堆

给出一组数据{12,16,8,5,20,29,40,22}，将其建成大根堆。

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem=new int[10];
    }

    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i]=array[i];
            this.usedSize++;
        }
    }

    public void createHeap(){
        for (int parent = (this.usedSize-1-1)/2; parent >=0 ; parent--) {
        //向下调整
            siftDown(parent,this.usedSize);
        }
    }

向下调整

1. 让parent标记需要调整的节点，child标记parent的左孩子
2. 如果parent的左孩子存在，即满足:child < size，进入while循环
3. child+1<usedSize 判断是否有右孩子，并且elem[child]<elem[child+1] 判断出左右孩子的大小
4. 将parent与较小的孩子child比较。如果parent小于较小的孩子child，交换parent与较小的孩子child。
5. 调整可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2+1;

//parent 每颗子树调整的时候的起始位置
//usedSize 判断每颗子树什么时候调整结束
private void siftDown(int parent, int usedSize) {
        int child = 2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize && 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;
            }
        }
    }

堆的插入与删除

堆的插入

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)

public boolean isFull(){
        return usedSize == elem.length;
    }
public void push(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        siftUP(usedSize);
        usedSize++;
    }

2. 将最后新插入的节点向上调整，直到满足堆的性质

private void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }
//注意此时的child是数组下标
private void siftUP(int child) {
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

总结：

1. 先将元素插入到堆的末尾，即最后一个孩子
2. 插入之后如果不满足堆的性质，将插入的节点向上调整到合适位置即可
   

堆的删除

1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整

public int poll(){
        int val=elem[0];
        swap(elem,0,usedSize-1);
        siftDown(0,usedSize-1);
        usedSize--;
        return val;
    }

PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

注意：
         1. 使用时必须导入PriorityQueue所在的包

import java.util.PriorityQueue;

         2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象

         3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

         4. PriorityQueue默认情况下是小根堆—即每次获取到的元素都是最小的元素

PriorityQueue的常用接口

优先级队列的构造

 // 创建一个空的优先级队列，底层默认容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();

// 创建一个空的优先级队列，底层的容量为initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);


ArrayList<Integer> list = new ArrayList<>();
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);

默认情况下，PriorityQueue队列是小根堆，如果需要大根堆需要用户提供比较器。

class IntCmp implements Comparator<Integer>{
  @Override
  public int compare(Integer o1, Integer o2) {
    return o2-o1;
 }
}

简单运用

插入元素

//插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，注意：空间不够时候会进行扩容
q.offer(e);

获取优先级最高的元素

System.out.println(q.peek());  

移除优先级最高的元素并返回

q.poll();

清空

q.clear();

源代码

static void PriorityQueue(){
  int[] arr = {4,1,9,2,8,0,7,3,6,5};
  // 一般在创建优先级队列对象时,建议就直接将底层容量给好

  // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
  PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
  for (int e: arr) {
    q.offer(e);//插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，注意：空间不够时候会进行扩容
 }
  System.out.println(q.size());  // 打印优先级队列中有效元素个数
  System.out.println(q.peek());  // 获取优先级最高的元素
  // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
  q.poll();
  q.poll();
  System.out.println(q.size());  // 打印优先级队列中有效元素个数
  System.out.println(q.peek());  // 获取优先级最高的元素
  q.offer(0);
  System.out.println(q.peek());  // 获取优先级最高的元素
  // 将优先级队列中的有效元素删除掉，检测其是否为空
  q.clear();
  if(q.isEmpty()){
    System.out.println("优先级队列已经为空!!!");
    }
  else{
    System.out.println("优先级队列不为空");
 }
}

完结

好了，到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，避免找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java

下期预告: 【Java数据结构】- - -Java比较