边学边记——数据结构☞堆（包括优先级队列的介绍）

迷南。 2023-09-30 16:23 2阅读 0赞

**目录**

一、堆（二叉堆）

堆是用来干什么的？

堆是用什么存储结构存储的？

1. 堆的概念

2. 堆的性质

3. 堆的存储方式

下标之间的规则：

4. 堆的基本操作

(1). 向下调整/堆化操作

(2).堆的创建

(3).堆的插入

(4).堆的删除

(5). 堆最主要的应用：优先级队列（假设小堆）

二、常用接口介绍

1. PriorityQueue的特性

2.PriorityQueue常用接口介绍

(1).优先级队列的构造

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

三、堆的应用

1.PriorityQueue的实现

2.堆排序

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

## 一、堆（二叉堆） ##

### 堆是用来干什么的？ ###

> 在一组不断变化的（随时在添加，删除元素）集合中，快速找到 "最值" （最大值or最小值）。

### 堆是用什么存储结构存储的？ ###

> 二叉树结构存储。假设使用线性链表结构进行维护，添加和删除的时间复杂度是O(1)，但是想找到此刻的最大值，只能进行遍历，时间复杂度为O(n)。

**补充：**二叉树是可以使用顺序结构进行维护的，但更适合完全二叉树。

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

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

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

>  *  逻辑上一颗完全二叉树（不需要按照链式结构进行组织，所以没有结点的概念），而是采用顺序结构进行组织。
>  *  物理存储上表现为一个数组（顺序表 数字+元素个数）。

**同时要求这颗完全二叉树做到：**

*  大堆——同时要求这颗完全二叉树，做到任取一个树上的元素，都大于等于其两个孩子的值。
 *  小堆——这颗完全二叉树，做到任取一个树上的元素，都小于等于其两个孩子的值。

**注意：物理视角——根本没有结点存在！**

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

堆是一颗**完全二叉树**，因此可以**层序**的规则采用**顺序**的方式来高效存储。

![f4ab38c57e4b40d4b290785c2b94f1c1.png][]

#### **下标之间的规则：** ####

>  *  假如我们已知一个元素的下标是\[k\]，则这个元素的左孩子的下标一定是\[2 \* k + 1\]，右孩子的下标一定是\[2 \* k + 2\]。
>  *  假如我们已知一个元素的下标是\[k\]，则这个元素的双亲的下标一定是：\[(k - 1) / 2\]。

PS：如果这个元素是其双亲的左孩子那么双亲下标：\[(k - 1) / 2\]；右孩子：\[(k - 2) / 2\]。但是向下取整就是((k - 1) / 2)（计算机中的除法本身就是向下取整）。

语言表达上使用树的概念：根，左孩子，右孩子，叶子...但是实际代码层面都是下标的处理，数组的处理。

### 4. 堆的基本操作 ###

#### (1). 向下调整/堆化操作 ####

**a. 前提**

> 完全二叉树基本已经满足堆的性质，只有进行操作的元素位置和其孩子的关系还不明确（也许满足，也许不满足），只有满足这个前提，才能进行向下调整操作。
> 
> 要进行向下调整操作，需要：
> 
>  *  满足前提的"堆"：long\[\] array，int size
>  *  要操作的位置：int index

**b. 操作（以小堆为例）**

**前提：**"我" ：待调整元素，"我" 不是叶子—>"我" 有孩子。

**步骤：**

1. 找到最小的孩子（可能是左孩子可能是右孩子）

2. 比较"我"和最小孩子的大小

*  "我" <= 最小的孩子 —> 满足堆的性质，调整停止
 *  "我" > 最小的孩子 —> 交换"我"和最小的孩子

3. 交换后，条件可能满足，可能不满足，若不满足，返回上述步骤，继续交换。

最坏情况："我“是根位置，最后调整至叶子位置。

图例：

![d9ea09c4632c45c79603770f9f9a6d3c.png][]

向下调整：

![e1da2313d6944917b0d20a0de39225b2.png][]

代码参考（小堆）：

public void shiftDown(int[] array, int parent) {
        // child先标记parent的左孩子，因为parent可能右左没有右
        int child = 2 * parent + 1;
        int size = array.length;
        while (child < size) {
            // 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
            if(child+1 < size && array[child+1] < array[child]){
                child += 1;
            }
            // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
            if (array[parent] <= array[child]) {
                break;
            }else {
                // 将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }

**c.复杂度**

> 数据规模n是size：
> 
>  *  时间复杂度：完全二叉树的高度：O(log2(n))
>  *  空间复杂度：非递归：O(1)；递归：O(n)

#### (2).堆的创建 ####

> 没有任何规律的数组（完全二叉树）变成一个堆：建堆的过程。

eg：对于普通的序列\{ 1,5,3,8,7,6 \}，该如何调整为大堆？

![da71801634bb456d8ae635b1f79488de.png][]![c33d6edafc6a4e46b0f7f3f8e806eac2.png][]![9619ec004fa6440fa17f3381f2d281bf.png][] ![e357ba0f4a6a4c41933c08d10ad409d5.png][]

![0a5222b172654d33bf769a2ebe823d8d.png][] ![14c39729cf0a4330a19dfaa3e9c738fa.png][]

![37ca1cf29d734f5a95a5d95e90caa67f.png][]

代码参考：

public static void createHeap(int[] array) {
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        int root = ((array.length-2)>>1);
        for (; root >= 0; root--) {
            shiftDown(array, root);
        }
    }

所以构造出来的大根堆为：\{8，7，6，5，1，3\}。

**建堆的时间复杂度：O(n)**

#### (3).堆的插入 ####

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

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

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

图例（小堆）：

![b82b9bc4f46b484e964939b007bbbe1b.png][]

向上调整代码参考（大堆）：

public void shiftUp(int child) {
        // 找到child的双亲
        int parent = (child - 1) / 2;
        while (child > 0) {
        // 如果双亲比孩子大，parent满足堆的性质，调整结束
            if (array[parent] > array[child]) {
                break;
            } else{
            // 将双亲与孩子节点进行交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
                child = parent;
                parent = (child - 1) / 1;
            }
        }
    }

#### (4).堆的删除 ####

**注意：堆的删除一定删除的是堆顶元素。**

具体如下：

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

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

3. 对堆顶元素进行向下调整

图例（ 小堆）：

![95824702694c47bab726a3dcf4dc5b6d.png][]

#### (5). 堆最主要的应用：优先级队列（假设小堆） ####

**a.操作**

>  *  插入（向上调整）
>  *  删除（最后一个元素放置堆顶，向下调整）
>  *  查看堆顶元素

**b.代码实现**

public class MyPriorityQueue {
        // 演示作用，不再考虑扩容部分的代码
        private int[] array = new int[100];
        private int size = 0;
    
        //插入
        public void offer(int e) {
            array[size++] = e;
            shiftUp(size - 1);
        }
    
        //删除
        public int poll() {
            int oldValue = array[0];
            array[0] = array[--size];
            shiftDown(0);
            return oldValue;
        }
        
        //查看堆顶元素
        public int peek() {
            return array[0];
        }
    }

## 二、常用接口介绍 ##

### 1. PriorityQueue的特性 ###

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里主要介绍PriorityQueue。

![67aaea92d6d5456f93a2cab1d224e979.png][]

关于PriorityQueue的使用要注意：

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

import java.util.PriorityQueue;

*  PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
 *  不能插入null对象，否则会抛出NullPointerException。
 *  没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
 *  插入和删除元素的时间复杂度为。
 *  PriorityQueue底层使用了堆数据结构。
 *  PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素。

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

#### (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>

**如果创建一个空的优先级队列，底层默认容量是11 ，但是一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好，否则在插入时需要不断的扩容。  
扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低。**

以下是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来进行扩容

**注意：**默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器（实现Comparator接口，然后重写接口中的compare方法即可）。

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

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

## 三、堆的应用 ##

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

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

### 2.堆排序 ###

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

(1).建堆

*  升序：建大堆
 *  降序：建小堆

(2).利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

此外，如果想改变默认的比较方式去完成一些操作，我们可以通过实现Comparable接口或者实现Comparator接口，关于他们的具体使用可以移步：

[关于对象的比较][Link 1]

如有建议或想法，欢迎一起讨论学习~

[f4ab38c57e4b40d4b290785c2b94f1c1.png]: https://img-blog.csdnimg.cn/f4ab38c57e4b40d4b290785c2b94f1c1.png
[d9ea09c4632c45c79603770f9f9a6d3c.png]: https://img-blog.csdnimg.cn/d9ea09c4632c45c79603770f9f9a6d3c.png
[e1da2313d6944917b0d20a0de39225b2.png]: https://img-blog.csdnimg.cn/e1da2313d6944917b0d20a0de39225b2.png
[da71801634bb456d8ae635b1f79488de.png]: https://img-blog.csdnimg.cn/da71801634bb456d8ae635b1f79488de.png
[c33d6edafc6a4e46b0f7f3f8e806eac2.png]: https://img-blog.csdnimg.cn/c33d6edafc6a4e46b0f7f3f8e806eac2.png
[9619ec004fa6440fa17f3381f2d281bf.png]: https://img-blog.csdnimg.cn/9619ec004fa6440fa17f3381f2d281bf.png
[e357ba0f4a6a4c41933c08d10ad409d5.png]: https://img-blog.csdnimg.cn/e357ba0f4a6a4c41933c08d10ad409d5.png
[0a5222b172654d33bf769a2ebe823d8d.png]: https://img-blog.csdnimg.cn/0a5222b172654d33bf769a2ebe823d8d.png
[14c39729cf0a4330a19dfaa3e9c738fa.png]: https://img-blog.csdnimg.cn/14c39729cf0a4330a19dfaa3e9c738fa.png
[37ca1cf29d734f5a95a5d95e90caa67f.png]: https://img-blog.csdnimg.cn/37ca1cf29d734f5a95a5d95e90caa67f.png
[b82b9bc4f46b484e964939b007bbbe1b.png]: https://img-blog.csdnimg.cn/b82b9bc4f46b484e964939b007bbbe1b.png
[95824702694c47bab726a3dcf4dc5b6d.png]: https://img-blog.csdnimg.cn/95824702694c47bab726a3dcf4dc5b6d.png
[67aaea92d6d5456f93a2cab1d224e979.png]: https://img-blog.csdnimg.cn/67aaea92d6d5456f93a2cab1d224e979.png
[Link 1]: https://blog.csdn.net/lil_ghost_/article/details/130317537?spm=1001.2014.3001.5501