java优先级队列(堆）

妖狐艹你老母 2023-09-27 11:54 158阅读 0赞

![在这里插入图片描述][0ec1043c39f54488a1daced60f3db7f8.gif_pic_center]

#### 文章目录 ####

*  一、优先级队列是什么？
 *  二、堆
 *   *  什么是堆？
     *  堆的分类：
     *  堆的存储
     *  堆的创建
 *  三、堆的操作
 *   *  插入元素
     *  弹出元素
 *  四、用堆模拟实现优先级队列

## 一、优先级队列是什么？ ##

在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优先级有关…  
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：

1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。  
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。

![在这里插入图片描述][31495508d08a46d381bb39d37db54f97.png]

## 二、堆 ##

### 什么是堆？ ###

堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为最大堆和最小堆。

堆性质：  
结构性：堆是一颗除底层外被完全填满的二叉树，底层的节点从左到右填入，这样的树叫做完全二叉树。即缺失结点的部分一定再树的右下侧。

堆序性：由于我们想很快找出最小元，则最小元应该在根上，任意节点都小于它的后裔，这就是小顶堆（Min-Heap）；如果是查找最大元，则最大元应该在根上，任意节点都要大于它的后裔，这就是大顶堆(Max-heap)。

### 堆的分类： ###

最大堆：父亲节点的值大于孩子节点的值  
最小堆：父亲节点的值小于孩子节点的值

> 将元素存储到数组中后，可以根据二叉树的性质对树进行还原。假设i为节点在数组中的下标，则有：  
> 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2  
> 如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子  
> 如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

### 堆的存储 ###

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储  
![在这里插入图片描述][bc39407f82714f5b941ecd27d6b48dfe.png]  
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节  
点，就会导致空间利用率比较低。

### 堆的创建 ###

我们创建堆是思路是：向下操作。

1.  让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
2.  如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在

> parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标  
> 将parent与较小的孩子child比较，如果：  
> parent小于较小的孩子child，调整结束  
> 否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子  
> 树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent\*2+1; 然后继续2。

public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public priorityQueue() {
        
            this.elem = new int[DEFAULT_SIZE];
        }
    
        /**
         * 建堆的时间复杂度为O(n)
         * 不能只看代码去猜测
         */
        public void createHeap(int[] array) {
        
            //检查数组容量，不够就进行扩容
            if(elem.length < array.length) {
        
                elem = Arrays.copyOf(elem, array.length  * 2);
            }
            for (int i = 0; i < array.length; i++) {
        
                elem[i] = array[i];
                usedSize++;
            }
            for (int i = (usedSize - 1 - 1) / 2; i >= 0; i--) {
        
                shiftDown(i,usedSize - 1);
            }
        }
    
        /**
         * 调整每颗子树的时间复杂度为O(log n)
         * root为每棵子树的根节点
         * len为每棵子树的结束条件
         * @return
         */
        private void shiftDown(int root,int len) {
        
            int child = root * 2 + 1;
            while(child <= len) {
        
                if(child + 1 < len && elem[child + 1] > elem[child]) {
        
                    child++;
                }
                if(elem[root] >= elem[child]) {
        
                    return;
                } else {
        
                    int h = elem[root];
                    elem[root] = elem[child];
                    elem[child] = h;
                    root = child;
                    child = root * 2 + 1;
                }
            }
        }

## 三、堆的操作 ##

### 插入元素 ###

/**
         * 入队之后要保证仍然为大根堆
         * 所以我们插入到最后位置，然后向上调整
         * @param val
         */
        public void push(int val) {
        
            //检查堆是否满了,满了进行扩容
            if(isFull()) {
        
                elem = Arrays.copyOf(elem,elem.length * 2);
            }
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize - 1);
        }
        private void shiftUp(int child) {
        
            int parent = (child - 1) / 2;
            while(child > 0) {
        
                if(elem[parent] >= elem[child]) {
        
                    return;
                }
                int h = elem[child];
                elem[child] = elem[parent];
                elem[parent] = h;
                child = parent;
                parent = (child - 1) / 2;
            }
        }

当我们要在堆中插入元素时，因为插入元素后仍然要保证二叉树是一个大堆，所以我们选择把元素插在末尾位置，先判断堆是否为满，如果为满先扩容。  
![在这里插入图片描述][54542898710540c4aa73ca84e28aaae9.png]  
用该位置元素和父亲元素比较，如果大于父亲元素，则交换父子元素，然后指向父亲的位置。  
![在这里插入图片描述][b4ec01c17065419d87c75aab57501eb0.png]  
在与该位置的父亲位置元素比较，如果父亲元素大则重复上述操作，否则插入结束。  
![在这里插入图片描述][57ac2864b22c40a3a125f7424d56332c.png]

### 弹出元素 ###

public void pollHeap() {
        
            //判断堆是否为空
            if(isEmpty()) {
        
                return;
            }
            int h = elem[0];
            elem[0] = elem[usedSize - 1];
            elem[usedSize - 1] = h;
            usedSize--;
            shiftDown(0,usedSize - 1);
        }

弹出元素和删除堆首元素的思路大致相同。时间复杂度为O(logn)  
![在这里插入图片描述][82930b26342f4be8bd066c3f0768afc0.png]  
先将堆尾元素和堆首元素进行交换，然后将usedSize–.  
![在这里插入图片描述][ed6985b7b3a6477f833a551be80261e2.png]  
接下来只需要对堆首元素向下操作即可。  
![在这里插入图片描述][b5761e0b2f224e22bff28b929b326f12.png]  
此时这个堆已经不符合最大堆的性质。为了保持这个性质，我们需要将堆顶的元素调整到它应该在的位置。也就是对它进行shift Down操作。在shift down时，因为它有左右孩子两个节点，所以我们需要将左右两个孩子节点进行比较，在得到较大的节点之后，再与它进行比较，如果它的子节点大，则将二者交换。并且不断的重复这样的操作，直到它没有叶子节点或者大于叶子节点停止。

![在这里插入图片描述][f26de67b0fce4bcd9cc18d16b89cc3ea.png]

![在这里插入图片描述][5f1c340ead354620a0f28029b6c51764.png]

## 四、用堆模拟实现优先级队列 ##

public class priorityQueue {
        
        public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public priorityQueue() {
        
            this.elem = new int[DEFAULT_SIZE];
        }
    
        /**
         * 建堆的时间复杂度为O(n)
         * 不能只看代码去猜测
         */
        public void createHeap(int[] array) {
        
            //检查数组容量，不够就进行扩容
            if(elem.length < array.length) {
        
                elem = Arrays.copyOf(elem, array.length  * 2);
            }
            for (int i = 0; i < array.length; i++) {
        
                elem[i] = array[i];
                usedSize++;
            }
            for (int i = (usedSize - 1 - 1) / 2; i >= 0; i--) {
        
                shiftDown(i,usedSize - 1);
            }
        }
    
        /**
         * 调整每颗子树的时间复杂度为O(log n)
         * root为每棵子树的根节点
         * len为每棵子树的结束条件
         * @return
         */
        private void shiftDown(int root,int len) {
        
            int child = root * 2 + 1;
            while(child <= len) {
        
                if(child + 1 < len && elem[child + 1] > elem[child]) {
        
                    child++;
                }
                if(elem[root] >= elem[child]) {
        
                    return;
                } else {
        
                    int h = elem[root];
                    elem[root] = elem[child];
                    elem[child] = h;
                    root = child;
                    child = root * 2 + 1;
                }
            }
        }
    
        /**
         * 入队之后要保证仍然为大根堆
         * 所以我们插入到最后位置，然后向上调整
         * @param val
         */
        public void push(int val) {
        
            //检查堆是否满了,满了进行扩容
            if(isFull()) {
        
                elem = Arrays.copyOf(elem,elem.length * 2);
            }
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize - 1);
        }
        private void shiftUp(int child) {
        
            int parent = (child - 1) / 2;
            while(child > 0) {
        
                if(elem[parent] >= elem[child]) {
        
                    return;
                }
                int h = elem[child];
                elem[child] = elem[parent];
                elem[parent] = h;
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    
        public void pollHeap() {
        
            //判断堆是否为空
            if(isEmpty()) {
        
                return;
            }
            int h = elem[0];
            elem[0] = elem[usedSize - 1];
            elem[usedSize - 1] = h;
            usedSize--;
            shiftDown(0,usedSize - 1);
        }
        public boolean isFull() {
        
            return usedSize == elem.length;
        }
    
        public boolean isEmpty() {
        
            return usedSize == 0;
        }
    
        public int peekHeap() {
        
            //判断堆是否为空
            if(isEmpty()) {
        
                return -1;
            }
            return elem[0];
        }
    }

[0ec1043c39f54488a1daced60f3db7f8.gif_pic_center]: https://img-blog.csdnimg.cn/0ec1043c39f54488a1daced60f3db7f8.gif#pic_center
[31495508d08a46d381bb39d37db54f97.png]: https://img-blog.csdnimg.cn/31495508d08a46d381bb39d37db54f97.png
[bc39407f82714f5b941ecd27d6b48dfe.png]: https://img-blog.csdnimg.cn/bc39407f82714f5b941ecd27d6b48dfe.png
[54542898710540c4aa73ca84e28aaae9.png]: https://img-blog.csdnimg.cn/54542898710540c4aa73ca84e28aaae9.png
[b4ec01c17065419d87c75aab57501eb0.png]: https://img-blog.csdnimg.cn/b4ec01c17065419d87c75aab57501eb0.png
[57ac2864b22c40a3a125f7424d56332c.png]: https://img-blog.csdnimg.cn/57ac2864b22c40a3a125f7424d56332c.png
[82930b26342f4be8bd066c3f0768afc0.png]: https://img-blog.csdnimg.cn/82930b26342f4be8bd066c3f0768afc0.png
[ed6985b7b3a6477f833a551be80261e2.png]: https://img-blog.csdnimg.cn/ed6985b7b3a6477f833a551be80261e2.png
[b5761e0b2f224e22bff28b929b326f12.png]: https://img-blog.csdnimg.cn/b5761e0b2f224e22bff28b929b326f12.png
[f26de67b0fce4bcd9cc18d16b89cc3ea.png]: https://img-blog.csdnimg.cn/f26de67b0fce4bcd9cc18d16b89cc3ea.png
[5f1c340ead354620a0f28029b6c51764.png]: https://img-blog.csdnimg.cn/5f1c340ead354620a0f28029b6c51764.png