Java——优先级队列（堆）_java中的大顶堆优先队列

概念

1. 普通的队列是先进先出的，但是优先级队列则按照优先级最高的元素出队列。
2. 而在Java中，优先级队列是使用了堆进行存储，堆就是在完全二叉树的逻辑基础上，对数据的顺序进行调整。
3. 根节点的值大于它的两个孩子节点的堆叫做大堆，相反则为小堆

堆的创建

由于堆是一颗完全二叉树，也就是层序遍历时数据之间不会掺杂null，因此一般用数组来存储堆

向下调整

将根节点的值和他的孩子进行比较，如果是大根堆，那么如果根节点的值比孩子中的任意一节点小，那么就将根节点向下调整。由于调整的只是一部分子树，因此需要将孩子的值赋给父亲，再进行向下调整，直到父亲不再有孩子。

public void shiftDown(int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < usedSize && arr[child] < arr[child + 1]){
                child++;//get max child
            }
            if(arr[child] > arr[parent]){
                swap(arr,child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整代码

import java.util.Arrays;

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

    public TestHeap(){
        arr = new int[10];
        usedSize = 0;
    }

    public void initArray(int[] array){
        arr = Arrays.copyOf(array,array.length);
        usedSize = array.length;
    }

    public void merge(){
        for (int i = (usedSize - 2) / 2; i >= 0 ; i--) {
            shiftDown(i,usedSize);
        }
    }
    public void shiftDown(int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < usedSize && arr[child] < arr[child + 1]){
                child++;//get max child
            }
            if(arr[child] > arr[parent]){
                swap(arr,child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

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

我们建堆的原理是从最后一个父亲节点开始，一直向下调整到根节点

建堆的时间复杂度

设树的高度是h，那么第一层一共有2 ^ 0个节点，需要向下调整h - 1次，第二层就是2 ^ 1个节点，需要往下调整h - 2次
因此，我们通过错位相减法，可以得到建堆的时间复杂度大约是n

堆的插入和删除

插入

由于堆的建立是有一定顺序的，因此在插入元素时不能只把要插入的元素放到数组的最后一位就结束，而是要调整堆的存储的顺序。
我们使用向上调整的方法，先讲元素放到最后一位，再与其父亲进行比较，如果比父亲大就和父亲交换，然后换后再让自己作为孩子，继续和上面的父亲进行比较。直到换到根的位置处。

删除

由于堆的优先级的存在，因此出堆的一定是位于根位置的元素。因此出堆后还需要对堆的结构进行调整。
因为如果要将整个堆重新建堆的时间复杂度较高，我们采用一种巧妙的方法——先记录堆顶元素的值，再将数组的最后一个元素放到根处，然后把根向下调整。
最后让usedSize–

由此可见，插入和删除元素的时间复杂度是logN

完整代码

public void offer(int x){
        if(isFull()){
            arr = Arrays.copyOf(arr,arr.length * 2);
            arr[usedSize] = x;
            usedSize++;
            shiftUp(usedSize - 1);
        }
    }
    public void shiftUp(int child ){
        int parent = (child - 1) / 2;
        while(child > 0){
            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize == arr.length;
    }

    public int poll(){
        if (isEmpty()){
            return -1;
        }
        int root = arr[0];
        arr[0] = arr[usedSize--];
        shiftDown(0,usedSize);
        return root;
    }
    public boolean isEmpty(){
        return usedSize == 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
28
29
30
31
32
33
34
35
36

PriorityQueue

简介

1. 是线程不安全的
2. 导入的包import java.util.PriorityQueue;
3. 传入的元素需要能比较大小
4. 不能插入null
5. 默认是小堆

构建方法

使用实例如下：

import java.util.Comparator;
import java.util.PriorityQueue;
class Student implements Comparable{
    int age;

    @Override
    public int compareTo(Object o) {
        return 0;
    }
}

class AgeComparator implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return 0;
    }
}
public class testDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(1);
        priorityQueue.offer(3);
        priorityQueue.offer(7);
        priorityQueue.offer(13);
        priorityQueue.offer(100);
        priorityQueue.offer(87);

        PriorityQueue<Student> studentPriorityQueue = new PriorityQueue<>(new AgeComparator());
        studentPriorityQueue.offer(new Student());
        studentPriorityQueue.offer(new Student());
    }
}
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

其他方法