优先级队列【堆】——数据结构

优先级队列（Priority Queue）

优先级队列：不同于先进先出队列，每次从队列中取出的是具有最高优先权的元素。
优先级队列相对于普通队列应该提供两个最基本的操作
（1） 返回最高优先级对象（2）添加新对象
在JDK8中的优先级队列底层使用了 堆

堆的概念

堆的实质就是一个完全二叉树——并且堆中的节点遵循某个结点的值总是不大于或不小于其父结点的值
因此堆分为 大根堆和小根堆

小堆：根节点最小的堆，满足Ki <= K2i+1 且 Ki <= K2i+2

大堆：根节点最大的堆, 满足Ki >= K2i+1 且 Ki >= K2i+2
如图：

堆的存储方式

堆是一棵完全二叉树，所以按照层序来看，可以采用顺序数组的存储方式

但是非完全二叉树就不适用于顺序存储了，因为非完全二叉树可能存在空节点，那么顺序存储也就存储这个空节点，造成空间上的浪费

i表示孩子结点，父亲结点**（i-1）/ 2**

i表示根节点 ，左孩子 2 * i + 1 右孩子 2 * i + 2

堆的创建（大根堆）

用堆模拟实现优先级队列（大根堆）

按顺序存储的方式，先写一个数组

   public int[] elem;
    public int userSize;//当前堆中有效的元素数据个数
 
    public MyHeap() {
        this.elem = new int[10];
        this.userSize = 0;
    }
 
    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        userSize = elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12

1. 创建堆
   具体代码实现：

  /**
     * @param parent: 每颗子树的根节点下标
     * @param len:每颗子树的结束位置
     * @description 向下调整
     */
    private void shiftDown(int parent,int len) {
        int child = 2*parent+1;//左孩子
        //必须要有左孩子
        while(child < len) {
            //如果一定有右孩子。那就判断 左孩子和右孩子大小，谁大保存谁
            if(child + 1 < userSize && elem[child] < elem[child+1]) {
                child++;
            }
            //交换 比较孩子和根大小交换 然后根节点往下走继续必须
            if (elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
        //交换  比较孩子和根大小交换
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     *建堆：大根堆
     *时间复杂度O(n)
     */
    public void createHeap() {
        for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,userSize);
        }
    }
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

分析一下建堆的时间复杂度O(n)

2. 堆的插入
   具体代码：

    public boolean isFull() {
        return userSize == elem.length;
    }
     //向上调整
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
        //堆的插入
    public void offer(int x) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[userSize] = x;
        userSize++;
        shiftUp(userSize-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

3. 堆的删除**（优先级队列删除，只能删除堆顶的元素）**
   具体代码：

    public boolean isEmply() {
        return userSize == 0;
    }
      //堆的删除  只能删除堆顶元素
    public int poll() {
        if (isFull()) {
            return -1;
        }
        int old = elem[0];
        //1.交换
        swap(elem,0,userSize-1);
        //2.有效元素个数-1
        userSize--;
        //3.栈顶元素向下调整
        shiftDown(0,userSize);
        return old;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

课后作业题

1.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是

2.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是 ()
A: [3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8] B: [2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8]
C: [2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6] D: [2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8]
经过变换得到的结果如图:
最小堆结果为 [2 3 4 5 7 8 6 ]

这篇笔记就先写到这里,因为在慢慢补,后面的内容也会慢慢做笔记,循序渐进吧,关于优先级队列还有一些内容放到明天早上肝吧.加油,小孙!!!