优先级队列

￡神魔★判官ぃ 2024-03-27 15:46 68阅读 0赞

**目录**

1.优先级队列

2.优先级队列的模拟实现

2.1堆的概念

2.2堆的创建

2.2.1堆向下调整

2.2.2堆的创建

2.2.3堆的时间复杂度

2.3堆的插入和删除

2.3.1插入

2.3.2删除

2.4用堆模拟实现优先级队列

3.接口介绍

3.1PriorityQueue的特性

3.2 PriorityQueue常用接口介绍

--------------------

## 1.优先级队列 ##

优先级队列的两个基本操作：

1.返回最高优先级对象

2.添加新的对象

## 2.优先级队列的模拟实现 ##

### 2.1堆的概念 ###

堆是一块完全二叉树，共有两种：

1.大根堆：根节点总是小于左右孩子

2.小根堆：根节点总是大于左右孩子

### 2.2堆的创建 ###

#### 2.2.1堆向下调整 ####

一个集合怎么创建成堆呢？

通过根节点向下调整（已大根堆为例）

1.令parent标记要调整的结点，child标记parent的左孩子

2.如果左孩子存在（child<size）,进行操作，直到parent没有左孩子

a.如果右孩子存在，则应令child=左右孩子中的最大的孩子

b.parent大于较大的孩子，结束；否则，parent和child交换，继续向下调整

![3a740902fc0d45ca9f16b984a5778134.png][]

以27为根的左右子树，都满足大根堆的性质，只有根节点不满足，所有只用将根节点向下调整就行。58>55,58>27，所以58和27交换；45>44,45>27，所以45和27交换。

注：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

#### 2.2.2堆的创建 ####

找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应当向下调整

#### 2.2.3堆的时间复杂度 ####

堆是完全二叉树。

设树的高度为h:

第一层，2^0个结点，要向下移动h-1层；

第二层，2^1个结点，要向下移动h-2层；

......

第h-1层，2^(h-2)个结点，要向下移动层；

则要移动的总步数为：

T（n）=2^0\*(h-1)+2^1\*(h-2)+....+2^(h-2)\*1约等于n

### 2.3堆的插入和删除 ###

#### 2.3.1插入 ####

步骤：

1.放在底层空间中（要考虑扩容）

2.将新插入的结点向上调整

![357b90764ea84d16becad6d02fdbd140.png][]

#### 2.3.2删除 ####

注：堆删除一定是堆顶元素

步骤：

1.将堆顶元素和堆中最后一个元素交换

2.将堆中有效数据个数减一

3.将堆顶元素向下调整

![0d5f59bba1cd4c009b059532667d1b92.png][]

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

public class PriorityQueue {
        public int[] elem;
        public int usedSize;
    
        public PriorityQueue() {
            this.elem = new int[10];
        }
    
        public void initElem(int[] array) {
            for (int i = 0; i < array.length; i++) {
                elem[i] = array[i];
                usedSize++;
            }
        }
    
        public void createHeap(int[] array) {
            for (int parent = (usedSize - 2) / 2; parent >= 0; parent--) {
                shiftDown(parent, usedSize);
            }
        }
    
        public void shiftDown(int parent, int len) {
            int child = 2 * parent + 1;
            while (child < len) {
                if (child + 1 < len && elem[child] < elem[child + 1]) {
                    child++;
                }
                if (elem[parent] < elem[child]) {
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    parent = child;
                    child = 2 * parent + 1;
                }
            }
        }
    
        /**
         * 入队：仍然要保持是大根堆
         *
         * @param val
         */
        public void offer(int val) {
            if (isFull()) {
                elem = Arrays.copyOf(elem, 2 * elem.length);
            }
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize - 1);
    
        }
    
        private boolean isFull() {
            return usedSize == elem.length;
        }
    
        private void shiftUp(int child) {
            int parent = (child - 1) / 2;
            while (child > 0) {
                if (elem[child] > elem[parent]) {
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
                    break;
                }
            }
        }
    
            /**
             * 出队【删除】：每次删除的都是优先级高的元素
             * 仍然要保持是大根堆
             */
            public void poll(){
                if(isEmpty()){
                    return ;
                }
                int tmp=elem[0];
                elem[0]=elem[usedSize-1];
                elem[usedSize-1]=tmp;
                usedSize--;
                shiftDown(0,usedSize);
            }
           
            public boolean isEmpty(){
                return usedSize==0;
            }
            /**
             * 获取堆顶元素
             * @return
             */
            public int peek(){
                if(isEmpty()){
                    return -1;
                }
                return elem[0];
            }
    
        
    }

## 3.接口介绍 ##

### 3.1PriorityQueue的特性 ###

1.使用时必须导入PriorityQueue所在的包，即：

> import java.util.PriorityQueue;

2.PriorityQueue中放置的元素必须要能够比较大小

3.插入和删除元素的时间复杂度为O(log2N)

4.PriorityQueue底层使用了堆数据结构

5.PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

### 3.2 PriorityQueue常用接口介绍 ###

1. 优先级队列的构造

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>构造器</td> 
   <td>功能</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue()</td> 
   <td>创建一个空的优先级队列，容量为11</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(int initialCapacity)</td> 
   <td>创建一个初识容量为initialCapacity的优先级队列，initialCapacity不能为空</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(Collection&lt;? extends E&gt;c)</td> 
   <td>用一个集合创建优先级队列</td> 
  </tr> 
 </tbody> 
</table>

public static void main(String[] args) {
            PriorityQueue<Integer> p=new PriorityQueue<>();
    
            PriorityQueue<Integer> p1=new PriorityQueue<>(100);
    
            ArrayList<Integer> list=new ArrayList<>();
            list.add(1);
            list.add(2);
            PriorityQueue<Integer> p2=new PriorityQueue<>(list);
        }

2. 插入/删除/获取优先级最高的元素

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>函数名</td> 
   <td>功能</td> 
  </tr> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td> <p>插入元素e,插入成功返回true,如果e为空，则空指针异常</p> <p>时间复杂度为O(log2N)</p> </td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取优先级最高的元素，如果为空，返回null</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>移除优先级最高的元素，如果为空，返回null</td> 
  </tr> 
  <tr> 
   <td>itn size()</td> 
   <td>返回有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>判空</td> 
  </tr> 
 </tbody> 
</table>

public static void main(String[] args) {
            int[] array={4,2,5,8,6,7,9,1};
            PriorityQueue<Integer> p=new PriorityQueue<>(array.length);
            for (int x: array) {
              p.offer(x);
            }
            System.out.println(p.size());
            System.out.println(p.poll());
            System.out.println(p.peek());
            p.clear();
            if(p.isEmpty()){
                System.out.println("优先级队列已经为空!!!");
            }else{
                System.out.println("优先级队列不为空!!!");
            }
        }

> 8  
> 1  
> 2  
> 优先级队列已经为空!!!

[3a740902fc0d45ca9f16b984a5778134.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d04a05051fe447f2b6fa9a62843dca06.png
[357b90764ea84d16becad6d02fdbd140.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b345c3ffeef141d88973832268196dcd.png
[0d5f59bba1cd4c009b059532667d1b92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dbabbc9c8d024c97b0ae71601d793308.png