数据结构-------优先级队列，堆

Myth丶恋晨 2023-09-27 14:04 24阅读 0赞

**目录**

一.堆

1.堆的概念

2.堆的性质：

3.堆的存储方式

4.堆的创建

4.1堆向下调整

4.2建堆

5.堆的插入与删除

5.1 堆的插入

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)

2. 将最后新插入的节点向上调整，直到满足堆的性质

以小根堆为例 :

5.2 堆的删除

二.优先级队列PriorityQueue

引入：

1.PriorityQueue简介

大小关系：

继承关系：编辑

2.常用接口介绍

2.1PriorityQueue的特性

2.2关于PriorityQueue的使用要注意：

2.3 PriorityQueue常用接口介绍

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

4.以下是JDK 1.8中，PriorityQueue的扩容方式

三.堆的应用

1.PriorityQueue的实现

2.堆排序

3.Top-k问题

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

## 一.堆 ##

### 1.堆的概念 ###

如果有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

（简单理解为：完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列\{k1,k2,…,kn\}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。）

### 2.堆的性质： ###

*  堆中某个节点的值总是不大于或不小于其父节点的值；
 *  堆总是一棵完全二叉树。

![f92f38990e5a4006b2e04d6880260ff0.png][]

### 3.堆的存储方式 ###

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。  
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

*  **如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2**
 *  **如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子**
 *  **如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子**

### 4.堆的创建 ###

#### 4.1堆向下调整 ####

对于集合\{ 27,15,19,18,28,34,65,49,25,37 \}中的数据，如果将其创建成堆呢？

首先需要按照层次遍历的方法把数组变成一课完全二叉树

![ea4051ae834646949f18ee7b3d5ff01f.png][]

**向下过程(以小堆为例)：  
1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)  
2. 如果parent的左孩子存在，即:child < size， 进行以下操作，判断parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行比较，找出较大的孩子，置为child，直到parent的左孩子不存在。  
3.将parent与较小的孩子child比较，如果：parent小于较小的孩子child，调整结束。 否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent\*2+1; 然后继续步骤2。**

/*
        用向下调整的方法建堆
        需要父节点和每棵树的结束结点的下标
        所有结束结点都不会超过数组长度，否则会越界
         */
        private void shiftDown ( int parent ,int len){
             int child = parent * 2 + 1;
             //有左子树,这是这个循环最基础的条件
             while (child < len){
                 //有右子树，且保证child的值是左右孩子的最大值
                 if (child+1 < len && arr[child + 1] > arr[child]) {
                     //左孩子小于有孩子，child变成右孩子
                     child++;
                 }
                 //比较父子结点的大小，保证
                 if (arr[child] > arr[parent]) {
                     int tem = arr[child];
                     arr[child] = arr[parent];
                     arr[parent] = arr[child];
                     //父，子 结点向下移，继续比较下一层子树
                     parent = child;
                     child = parent * 2 + 1;
                 }else {
                     break;
                 }
    
             }
        }

**最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O（log n）【向下调整的时间复杂度为：树的高度】**

#### 4.2建堆 ####

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

![6c77d7b23d034a9db44f7efff782bf4d.png][]

**因此：建堆的时间复杂度为O(N）**

### 5.堆的插入与删除 ###

#### 5.1 堆的插入 ####

> #### 堆的插入总共需要两个步骤： ####
> 
> #### 1. 先将元素放入到底层空间中(注意：空间不够时需要扩容) ####
> 
> #### 2. 将最后新插入的节点向上调整，直到满足堆的性质 ####

#### 以小根堆为例 : ####

![fbb655eae5a945c4bfad33c2bd0d95fc.png][]

public void offer (int val){
            //判断是否越界，如果越界进行扩容
            if (isFull()){
                arr = Arrays.copyOf(arr,2*arr.length);
            }
            //把新插入的结点放到有效结点的最后
            arr[usedSize++] = val;
            //向上调整
            shiftUp(usedSize-1);
    
        }
        public void shiftUp(int child){
            int parent = (child - 1) / 2 ;
            while(child > 0){
    //如果如果双亲比孩子小，交换双亲与孩子结点，如果双亲比孩子大，parent满足堆的性质，调整结束
                if(arr[child] > arr [parent]){
                    int tem = arr[child];
                    arr[child] = arr [parent];
                    arr [parent] = tem;
                    //向上移动child 和parent
                    child = parent;
                    parent = (child-1)/2;
                }else {
                    break;
                }
                }
    
            }

#### 5.2 堆的删除 ####

> 注意：堆的删除一定删除的是堆顶元素。具体如下：  
> 1. 将堆顶元素对堆中最后一个元素交换  
> 2. 将堆中有效数据个数减少一个  
> 3. 对堆顶元素进行向下调整

**以小顶堆为例：**

![4c9a9824e9a44a8295b6a87720396014.png][]

public void pop (){
            if (isEmpety()){
                return ;
            }
            //第一个和最后一个交换
            swap(arr,0,usedSize-1);
            //删了一个，长度减一
            usedSize--;
            //向下调整
            shiftDown(0,usedSize);
        }
        public boolean isEmpety(){
            return usedSize == 0 ;
        }
        //交换
        public void  swap (int[] array, int i ,int j){
            int tem = arr[i];
            arr[i] = arr [j];
            arr [j] = tem;
    
        }

## 二.优先级队列**PriorityQueue** ##

### 引入： ###

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队  
列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。  
在这种情况下，**数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。**

### **1.PriorityQueue简介** ###

**PriorityQueue，即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素（Java优先级队列默认每次取出来的为最小元素）。**

#### **大小关系：** ####

**元素的比较可以通过元素本身进行自然排序，也可以通过构造方法传入比较器进行比较。**

#### 继承关系：   ![76eeaa10f9664ffab1ad62261e69e569.png][] ####

**通过继承关系图可以知道PriorityQueue是Queen接口的一个实现类，而Queen接口是Collection接口的一个实现类，因此其拥有Collection接口的基本操作。**

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整

PriorityQueue示例

> import java.util.PriorityQueue;
> 
> public class PriorityQueueTest01 \{  
> public static void main(String\[\] args) \{  
> PriorityQueue<Integer> queue = new PriorityQueue<>();  
> queue.add(11);  
> queue.add(33);  
> queue.add(22);  
> queue.add(55);  
> queue.add(44);
> 
> System.out.println(queue.remove());  
> System.out.println(queue.remove());  
> System.out.println(queue.remove());  
> System.out.println(queue.remove());  
> System.out.println(queue.remove());  
> \}  
> \}  
>

运行结果：![7b1c50b52817433897e64bf53e5b70b1.png][]

### 2.常用接口介绍 ###

#### 2.1PriorityQueue的特性 ####

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列

PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍

PriorityQueue。

#### 2.2关于PriorityQueue的使用要注意： ####

>  *  **1. 使用时必须导入PriorityQueue所在的包，即：import java.util.PriorityQueue;**
>  *  **2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出**
>  *  **ClassCastException异常**
>  *  **3. 不能插入null对象，否则会抛出NullPointerException**
>  *  **4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容（其实也是有限制的，是数组的最大长度一个int，2147483647）**
>  *  **5. 插入和删除元素的时间复杂度为O(log2N）**
>  *  **6. PriorityQueue底层使用了堆数据结构**
>  *  **7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素**

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

**2.3.1. 优先级队列的构造**  
此处只是列出了PriorityQueue中常见的几种构造方式（其他的参考帮助文档）

<table> 
 <tbody> 
  <tr> 
   <td>构造器</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue()</td> 
   <td>创建一个空的优先级队列，默认容量是11</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(int<br> initialCapacity)</td> 
   <td>创建一个初始容量为initialCapacity的优先级队列，注意：<br> initialCapacity不能小于1，否则会抛IllegalArgumentException异<br> 常</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(Collection&lt;?<br> extends E&gt; c)</td> 
   <td>用一个集合来创建优先级队列</td> 
  </tr> 
 </tbody> 
</table>

>     static void TestPriorityQueue(){
>     // 创建一个空的优先级队列，底层默认容量是11
>     PriorityQueue<Integer> q1 = new PriorityQueue<>();
>     
>     
>     // 创建一个空的优先级队列，底层的容量为initialCapacity
>     PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
>     
>     
>     ArrayList<Integer> list = new ArrayList<>();
>     list.add(4);
>     list.add(3);
>     list.add(2);
>     list.add(1);
>     
>     
>     // 用ArrayList对象来构造一个优先级队列的对象
>     // q3中已经包含了三个元素
>     PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
>     System.out.println(q3.size());
>     System.out.println(q3.peek());
>     }
> 
> 注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器（后面讲）

**大顶堆的实现**

>     // 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
>     class IntCmp implements Comparator<Integer>{
>     @Override
>     public int compare(Integer o1, Integer o2) {
>     return o2-o1;//在这里控制实现大/小顶堆
>     }
>     }
>     public class TestPriorityQueue {
>     public static void main(String[] args) {
>     PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
>     p.offer(4);
>     p.offer(3);
>     p.offer(2);
>     p.offer(1);
>     p.offer(5
>     System.out.println(p.peek());
>     }
>     }
> 
> 此时创建出来的就是一个大堆

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

<table> 
 <tbody> 
  <tr> 
   <td>函数名</td> 
   <td>功能介绍</td> 
  </tr> 
  <tr> 
   <td>boolean<br> offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时<br> 间复杂度 ，注意：空间不够时候会进行扩容</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取优先级最高的元素，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>移除优先级最高的元素并返回，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>void<br> clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean<br> isEmpty()</td> 
   <td>检测优先级队列是否为空，空返回true</td> 
  </tr> 
 </tbody> 
</table>

#### **4.以下是JDK 1.8中，PriorityQueue的扩容方式**    ####

>     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
>     private void grow(int minCapacity) {
>     int oldCapacity = queue.length;
>     // Double size if small; else grow by 50%
>     int newCapacity = oldCapacity + ((oldCapacity < 64) ?
>     (oldCapacity + 2) :
>     (oldCapacity >> 1));
>     // overflow-conscious code
>     if (newCapacity - MAX_ARRAY_SIZE > 0)
>     newCapacity = hugeCapacity(minCapacity);
>     queue = Arrays.copyOf(queue, newCapacity);
>     }
>     private static int hugeCapacity(int minCapacity) {
>     if (minCapacity < 0) // overflow
>     throw new OutOfMemoryError();
>     return (minCapacity > MAX_ARRAY_SIZE) ?
>     Integer.MAX_VALUE :
>     MAX_ARRAY_SIZE;
>     }
> 
> 优先级队列的扩容说明：  
> 如果容量小于64时，是按照oldCapacity的2倍方式扩容的  
> 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的  
> 如果容量超过MAX\_ARRAY\_SIZE，按照MAX\_ARRAY\_SIZE来进行扩容  
>

### 三.堆的应用 ###

### 1.PriorityQueue的实现 ###

用堆作为底层结构封装优先级队列

### 2.堆排序 ###

> **堆排序即利用堆的思想来进行排序，总共分为两个步骤：  
> 1. 建堆  
> 升序：建大堆  
> 降序：建小堆  
> 2. 利用堆删除思想来进行排序  
> 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序**
> 
> **代码实现：（省略建堆过程）**  
> 
> 
>     public void heapSort(){
>             int end = usedSize-1;
>             while (end > 0 ){
>                 swap(arr,0,end);//交换
>                 shiftDown(0,end);//调整堆
>                 end--;
>             }
>         }
>     //交换方法
>         public void  swap (int[] array, int i ,int j){
>             int tem = arr[i];
>             arr[i] = arr [j];
>             arr [j] = tem;
>     
>         }
>     //向下调整
>         private void shiftDown ( int parent ,int len){
>              int child = parent * 2 + 1;
>              //有左子树,这是这个循环最基础的条件
>              while (child < len){
>                  //有右子树，且保证child的值是左右孩子的最大值
>                  if (child+1 < len && arr[child + 1] > arr[child]) {
>                      //左孩子小于有孩子，child变成右孩子
>                      child++;
>                  }
>                  //比较父子结点的大小，保证
>                  if (arr[child] > arr[parent]) {
>                      int tem = arr[child];
>                      arr[child] = arr[parent];
>                      arr[parent] = arr[child];
>                      //父，子 结点向下移，继续比较下一层子树
>                      parent = child;
>                      child = parent * 2 + 1;
>                  }else {
>                      break;
>                  }
>     
>              }
>         }

### 3.Top-k问题 ###

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。  
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。  
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

**最佳的方式就是用堆来解决，基本思路如下：**

> **1. 用数据集合中前K个元素来建堆  
> 前k个最大的元素，则建小堆  
> 前k个最小的元素，则建大堆  
> 2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素  
> 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。**
> 
> **以前K个最大的元素为例：**
> 
> **原理：前K个元素建立小根堆，则此时根节点最小，再插入新的结点与根节点比较，如果比根节点小则直接忽略，如果比根节点大，则替换根节点的位置，并将此堆重新建成小根堆，这样能保证堆中的元素永远是最大的前K个。**
> 
> **代码实现如下：**
> 
>     public static int[] maxK(int[] arr, int k) {
>             int[] ret = new int[k];
>             if (arr == null || k == 0) {
>                 return ret;
>             }
>             Queue<Integer> minHeap = new PriorityQueue<>(k);
>             //1.遍历数组的前k个元素，并放到堆中
>             for (int i = 0; i < k; i++) {
>                 minHeap.offer(arr[i]);
>             }
>                 //2.遍历剩下的元素，每次和堆顶比较，对顶元素小就把堆顶弹出，这个元素插入
>                 for (int i = k; i < arr.length; i++) {
>                     int val = minHeap.peek();
>                     if (val < arr[i]) {
>                         minHeap.poll();//弹出堆顶
>                         minHeap.offer(arr[i]);//插入元素
>                     }
>     
>                 }
>     
>                 for (int i = 0; i < k; i++) {
>                     ret[i] = minHeap.poll();
>                 }
>                 return ret;
>         }

[f92f38990e5a4006b2e04d6880260ff0.png]: https://img-blog.csdnimg.cn/f92f38990e5a4006b2e04d6880260ff0.png
[ea4051ae834646949f18ee7b3d5ff01f.png]: https://img-blog.csdnimg.cn/ea4051ae834646949f18ee7b3d5ff01f.png
[6c77d7b23d034a9db44f7efff782bf4d.png]: https://img-blog.csdnimg.cn/6c77d7b23d034a9db44f7efff782bf4d.png
[fbb655eae5a945c4bfad33c2bd0d95fc.png]: https://img-blog.csdnimg.cn/fbb655eae5a945c4bfad33c2bd0d95fc.png
[4c9a9824e9a44a8295b6a87720396014.png]: https://img-blog.csdnimg.cn/4c9a9824e9a44a8295b6a87720396014.png
[76eeaa10f9664ffab1ad62261e69e569.png]: https://img-blog.csdnimg.cn/76eeaa10f9664ffab1ad62261e69e569.png
[7b1c50b52817433897e64bf53e5b70b1.png]: https://img-blog.csdnimg.cn/7b1c50b52817433897e64bf53e5b70b1.png