数据结构 - 优先级队列（堆）_优先队列底层数据结构

---

前言

本篇PriorityQueue优先级队列的介绍其底层是堆，关于堆的认识，使用优先级队列能解决的一些问题；如有错误，请在评论区指正，让我们一起交流，共同进步！

---

本文开始

1.介绍优先级队列

优先级队列：它的底层是一种堆的数据结构，它以顺序结构存储，是一个一维数组；

既然底层是堆，就来了解一下！

2. 认识堆

认识堆的特点：有两种堆类型
① 小根堆：父节点小于左右孩子节点，不能保证左右孩子谁大； =》使用优先级队列就创建了小根堆，想要创建大根堆需要自己给比较器(根据自定义规则比较，用于节点交换)；
② 大根堆：父节点大于左右孩子节点，不能保证左右孩子谁大；
③ 堆还是完全二叉树：可以使用顺序存储；非完全二叉树存储，为了还原二叉树还需要存储空节点，浪费空间 - 》堆为什么可以顺序存储的原有；

代码实现小根堆：
向下调整(父节点向下走)：从最后一颗子树开始，父节点与子节点比较大小是否交换，直到不用比较就确定了小根堆；

    /**
     * 建堆的时间复杂度：
     * O(n)
     */
//求出最后一个父节点，因为是顺序存储的-1就是下一颗树的父节点
 public void createHeap(int[] array) {
        for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {
            //获取最后一个子树父节点，usedSize记录数组中存储的个数
            //传递父节点和孩子节点最大的范围
            shiftDown(parent,usedSize);
        }
    }

    /**
     * root 是每棵子树的根节点的下标
     *  len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn) ;最坏换树的高度
     */
    private void shiftDown(int root,int len) {
        //向下调整需要每个子树的父节点
        int child = 2 * root + 1;//求出左孩子节点位置
        while (child < len) {
            //获取孩子节点最大值下标
            //防止右孩子下标越界，需要判断
            if(child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //比较父子节点大小
            if(elem[child] > elem[root]) {
                swap(elem,child,root);
                //调整父子节点下标位置
                child = root;
                root = 2 * child + 1;//再次获取左孩子节点下标
            }else {
                //父节点大于子节点直接跳出
                break;
            }
        }
  }
    //交换函数
    private void swap(int[] elem, int child, int root) {
        int tmp = elem[child];
        elem[child] = elem[root];
        elem[root] = 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
44
45
46

代码实现大根堆
向上调整(孩子节点向上走)：

private void shiftUp(int child) {
        //求出它的父节点下标
        int parent = (child - 1) / 2;
        //child==0最后一个节点不用比较
        while (child > 0) {
            //比较父子节点大小
            if(elem[child] > elem[parent]) {
                //交换
                swap(elem,child,parent);
                //移动父子节点下标，可能不止移动一次（子节点向上）
                child = parent;
                parent = (child - 1) / 2;//获得更上一级的父节点下标
             }else {
                //父节点小于子节点直接跳出
                break;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 实现优先级队列

了解大根堆，小根堆就可以实现优先级队列！
代码实现优先级队列（以大根堆为例）：

public class PriorityQueue {
    public int[] elem;
    public int usedSize;
    public PriorityQueue() {
        int[] elem = new int[10];
    }

    //交换函数
    private void swap(int[] elem, int child, int root) {
        int tmp = elem[child];
        elem[child] = elem[root];
        elem[root] = tmp;
    }


    /**
     * 入队：仍然要保持是大根堆
     */
    public void push(int val) {
        //插入
        if(isFull()) {
            //扩增
            Arrays.copyOf(elem,2*elem.length);
            return;
        }
        //没满就在最后位置插入
        elem[usedSize] = val;
        //向上调整即可
        shiftUp(usedSize);
        usedSize++;
    }

   
    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出队删除：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
        if(isEmpty()) {
            return;
        }
        //交换首尾
        int end = usedSize - 1;
        swap(elem,0,end);
        //向下调整范围需要-1，因为删除了一个元素
        shiftDown(0,--usedSize);
    }
//判断是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素
     */
    public int peekHeap() {
        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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

3.1 了解优先级队列的构造方法：

① 无参构造：默认大小11

② 有一个整形参数的构造：

③ 两个参数(整形，比较规则)的构造：

3.2 使用优先级队列解决问题：

1.top-k问题：
例如取前k个最小 / 最大的值；
2.堆排序
①升序(1,2,3…)：大根堆
使用原因：大根堆堆顶元素一定最大的，将堆顶元素与堆末尾元素交换，再向下调整，重新得到大根堆；这样每次都会把最大的放到最后，再次到堆顶的时候，堆顶后面的元素已经有序了，依次弹出即可；
②降序(4,3,2…)：小根堆
使用原有：小根堆堆顶元素一定最小的，将堆顶元素与堆末尾元素交换，再向下调整，重新得小根堆；这样每次都会把最小的放到最后，再次到堆顶的时候，堆顶后面的元素已经降序有序了，依次弹出即可；

---

总结

✨✨✨各位读友，本篇分享到内容如果对你有帮助给个声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】