优先级队列（堆）【Java】

优先级队列

什么是优先级队列

所谓优先级队列，实际就是队列中的元素带有优先级；在一些特定的情形下，可能需要队列中的一些元素先出队，但由于普通队列先进先出的限制条件，我们无法得到这种结果，因此就需要元素带有优先级的优先级队列来解决这个问题。

优先级队列的结构

在JDK1.8中，优先级队列底层实际是采用了堆这种数据结构，而堆实际上就是二叉树的特殊情况：

优先级队列的模拟实现

什么是堆

有一个关键码的集合K = {k0，k1， k2，…，kn-1}，如果把它的所有元素按完全二叉树的顺序存储方式（层序遍历方式）存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，就称这是一个堆结构；
根节点的值始终大于孩子结点值的堆称为大根堆；
根节点的值始终小于孩子结点值的堆称为小根堆；

堆的特性

• 堆一定是一棵完全二叉树；
• 堆的根节点编号为0时，设堆的任意一棵树的根节点编号为i，则左孩子的编号为（2i+1）,右孩子编号为（2i+2）;孩子结点编号为i时，父亲结点为（i-1）/2；

堆的存储方式

由于堆是一棵完全二叉树，因此可以使用层序遍历的方式来顺序存储；

但是如果是一棵非完全二叉树，如果采用数组来顺序存储，数组的一些元素势必就是null，也就势必会造成空间的浪费；

建堆（以大根堆为例）

大体思路：首先堆作为一棵二叉树，必然有许多子树，我们就可以从一棵子树出发，首先根据数组元素下标与数组长度及完全二叉树孩子结点与根节点之间的关系，我们找到堆的最后一个根节点，从这个根节点出发，向下调整，向上遍历，在每一颗子树的调整过程中，首先比较孩子的左右结点，用左右孩子的最大值与根节点进行比较，在需要的情况下进行调换，每棵子树都如此即可建立一个大根堆（或小根堆）；
下面是具体的代码实现：

public class TreeHeap {
    //创建一个数组存储堆中的元素；
    public int [] elem;
    public int usedSize;    //记录当前数组的有效元素个数

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

    public void createHeap(int [] array){
        //准备初始数据
        for (int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            usedSize++;
        }

        //首先找到堆的最后一个结点
        for (int p=usedSize-1;p>=0;p-- ){
            shifDown(p,usedSize);
        }
    }
    public  void shifDown(int root,int len){
        int parent=root;
        int child=2*parent+1;   //通过孩子结点找到当前子树根节点的下标
        while (child<len){  //孩子结点的下标一定是小于数组长度的，以此确定当前子树调整的结束位置
            if (child+1<len&&elem[child]<elem[child+1]){   //找到左右孩子的最大值
                child++;
            }
            if (elem[child]<elem[parent]){  //孩子结点的值小于根节点时，当前子树不需要进行调整
                break;
            }
            //满足调整条件时，进行调整
            int tmp=elem[child];
            elem[child]=elem[parent];
            elem[parent]=tmp;

            //继续向下进行调整
            parent=child;
            child=2*parent+1;
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

关于这样一段代码，其时间复杂度又是如何呢？

堆的插入

给一个大根堆中插入元素，使插入之后整棵树依然是一个大根堆；
大体思路：为了整个程序的正确性，我们将插入的元素首先插入到当前堆的最后一个元素之后，在依据大根堆的特点对其进行调整即可；

public class TreeHeap {
    //创建一个数组存储堆中的元素；
    public int [] elem;
    public int usedSize;    //记录当前数组的有效元素个数

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

    //这里省略了建堆的操作

    public void push(int value){
        //如果数组已满，进行扩容
        if (isfull()==true){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        //将需要插入的元素插入到当前堆的最后
        elem[usedSize]=value;
        //调整为大根堆
        shiftUp(usedSize);
        usedSize++; //更新堆元素的个数
    }
    
    private void shiftUp(int child){
        int parent=(child-1)/2;     //根据公式推出当前子树的根
        while (child>0){    //其大于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(){
        if (elem.length==usedSize){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

堆的删除

出堆顶的第一个元素，操作完成以后仍然是一个大根堆；
大体思路：将堆顶元素与堆的最后一个元素交换，删除最后一个元素，调整当前堆为大根堆；

    public boolean isEmpty(){
        if (usedSize==0){
            return true;
        }
        return false;
    }
//出队
    public void poll(){
        //如果队列为空，无法进行删除
        if (isEmpty()){
            System.out.println("队列为空");
            return;
        }
        //交换堆顶元素和最后一个元素
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;     //删除
        shifDown(0,usedSize);   //调整为大根堆
    }
//查看队头元素
    public int peek(){
        if (isEmpty()){
            return -1;
        }
        return elem[0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

至此，一个优先级队列就实现啦，包括入队、出队、查看队头元素；基于我们手动实现的优先级队列，java自身提供的优先级队列又是如何呢？

PriorityQueue

java官方提供的优先级队列即PriorityQueue，首先是队列的默认容量：
默认容量为11；
然后是优先级的定义方式，借助了比较器来完成：
优先级队列的构造方法也是提供了许多种方式，下面是其构造方法之一：
这里实际是创建一个手动指定了初始容量值的队列，然后用指定了排序方式的比较器，如果初始容量小于0，将抛出非法数据异常；
然后关于优先级队列的建堆方式，我们可以手动进行测试：

根据运行结果，PriorityQueue默认建堆应该是一个小根堆；

然后是PriorityQueue的扩容机制：
定义oldCapacity为原队列的长度，如果原队列的长度小于64，进行二倍扩容（实际是2倍扩容再加2）；否则进行1.5倍扩容；
前面说到，PriorityQueue默认建堆是一个小根堆，那么有没有方式建立一个大根堆呢？
如果是建立一个大根堆，重新定义其比较方式即可，方法为：构造一个类重写Comparator的compare方法；
至此，优先级队列的基本内容就结束啦 over！