Java语言---PriorityQueue与堆

向右看齐 2024-04-20 14:25 72阅读 0赞

**目录**

一.堆

1.1堆的概念

1.2堆的存储方式

1.3堆的操作

1.3.1堆的创建

1.3.2代码的实现：

堆的插入元素

堆的删除

二、PriorityQueue

2.1概念

2.2性质

2.3PriorityQueue的创建构造

2.4PriorityQueue的操作方法

总结

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

> ?个人主页：[tq02的博客\_CSDN博客-C语言,Java,Java数据结构领域博主][tq02_CSDN_-C_Java_Java]  
> ?梦的目标：努力学习，向Java进发，拼搏一切，让自己的未来不会有遗憾。  
> ?欢迎各位→**点赞**? + **收藏**⭐ + **评论**?+**关注**✨  
> 本章讲解内容：堆与PriorityQueue 基于[二叉树的知识][Link 1]。
> 
> ![来源百度][9efc1f98e3a04f7ba348f9fe24741977.png] 来源于百度
> 
> 使用编译器：IDEA

## 一.堆 ##

### 1.1堆的概念 ###

> **堆**，也称优先级队列，是存放元素的集合。而所存放的元素按照 完全二叉树的顺序存储方式。堆中每个结点总是 不大于或不小于 其父结点。
> 
> **堆**分为2种：**大堆** **小堆**
> 
> ![e011a9118f7c485781b0377a39e79f64.png][]
> 
> 大堆： 父结点的值 大于 子结点，也就是根结点的值最大。
> 
> 小堆： 父结点的值 小于 子结点，也就是根结点的值最小。

### 1.2堆的存储方式 ###

虽然堆的存储方式按照完全二叉树，完全二叉树实现有2种方式(链表 或者 数组）。而此时因为堆的性质，使用一维数组的方式存储更为高效。**堆中元素层序存储到一维数组。**

**代码实现：**

public class MyHeap{
    
       public int[] array;
       public int capacity;   //数组容量
       public int index;  //数组大小
    
        MyHeap(){
        array=new int[10];
        this.capacity=10;
        this.index=0;
    }
        MyHeap(int num)
        {
        array=new int[num];
        this.capacity=num;
        this.index=0;
        }
    //向下调整结点方法
    public void shiftDown(int[] array, int parent);
    //插入新元素
    public void shiftUp(int[] array,int child);
    //删除堆顶元素
    public void delectHeap(int[] array)；

### 1.3堆的操作 ###

> 在使用Java语言操作 **堆** 之前，我们需要明确几个性质。
> 
> 1、堆是完全二叉树，除了最后一层，每一层的结点都是满的。
> 
> 2、当序号为 i 时
> 
>  *  如果i为0，则为根结点，否则i节点的父节点为 (i - 1)/2；
>  *  如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子
>  *  如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

#### 1.3.1堆的创建 ####

> 在堆中，我们很明显是需要将一个集合，变成**大堆**，或者**小堆**的。![cf85f99761404ce8af483bce5d31a616.png][]

此刻我们展开一下变大堆的过程：

![8535c9f7233443de8216b559d27002b6.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.

#### **1.3.2代码的实现：** ####

//向下调整结点方法
    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;
        }
        }
    }
    
    public void heapJust(int[] array)
    {
       for(int i=(array.length-1-1)/2;i>=0;i--)
        {
            shiftDown(array,i);
        }
    }

#### 堆的插入元素 ####

1. 先将元素放入到数组的最后一位中（二叉树的末端）(注意：空间不够时需要扩容)  
2. 将最后新插入的节点向上调整，直到满足堆的性质  
![e043e8601b6c4e888416604fb3b1b177.png][] 代码实现：

//该方法是传递已经添加了新元素的数组,以及末尾元素下标
    public void shiftUp(int[]array,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;
    }
    }
    }

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

删除的是堆顶元素，将堆顶元素与最后一位交换，将堆中有效数据个数减少一位，再进行向下调整。

![eee4f493834b46649d689701e11a0d98.png][]

代码实现：

public void delectHeap(MyHeap t)
    {
     int[] array1=t.array;       
     int i=array1.length-1;
    //swap方法，是交换数组元素
         swap(array1,i,0);
    //删除末尾元素
        array1[index]=0;
        t.index--;
    //堆顶元素再向下调整
        shiftDown(array1,0);
    }

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

## 二、PriorityQueue ##

### 2.1概念 ###

> 1、 PriorityQueue的类型是优先级队列，优先队列的作用是保证每次取出的元素都是队列中权值**最小/最大**的
> 
> 2、 PriorityQueue 是采用 **树形结构** 来描述元素的存储，具体说是通过完全二叉树实现一个小顶堆，在物理存储方面，PriorityQueue 底层通过 **数组** 来实现元素的存储。
> 
> 在集合框架中的联系：
> 
> ![10a2db83d3e74a868f2a9705a2e0a45f.png][]

### 2.2性质 ###

> 1、底层运用了 **堆** 数据结构，并且默认情况下，为小堆。
> 
> 2、默认情况下容量为11，无容量限制，内部可自动扩容。
> 
> 3、不可以插入无法比较的对象，会抛出异常。
> 
> 4、不可以插入null对象。
> 
> 注：因为默认情况为小堆，所以需要大堆时，需要用户提供比较器。

### 2.3PriorityQueue的创建构造 ###

> 三种构造方法：
> 
> <table style="width:600px;"> 
>  <tbody> 
>   <tr> 
>    <td style="width:297px;"><strong>构造器</strong></td> 
>    <td style="width:301px;"></td> 
>   </tr> 
>   <tr> 
>    <td style="width:297px;">PriorityQueue（）</td> 
>    <td style="width:301px;">创建一个空的优先级队列，默认容量：11</td> 
>   </tr> 
>   <tr> 
>    <td style="width:297px;">PriorityQueue( int capacity)</td> 
>    <td style="width:301px;">创建一个初始容量为capacity的优先级队列</td> 
>   </tr> 
>   <tr> 
>    <td style="width:297px;">PriorityQueue(Collection&lt;? extends E&gt; c）</td> 
>    <td style="width:301px;">用一个集合创建优先级队列</td> 
>   </tr> 
>  </tbody> 
> </table>

代码实例：

public void TestPriorityQueue(){
    // 创建一个空的优先级队列，底层默认容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    
    // 创建一个空的优先级队列，底层的容量为initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    
    
    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
    ArrayList<Integer> list = new ArrayList<>();
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.size());
    System.out.println(q3.peek());

### 2.4PriorityQueue的操作方法 ###

> 常用的方法：插入、删除、获取优先级最高（堆顶元素）
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td style="width:137px;"><strong>函数名</strong></td> 
>    <td style="width:361px;">&nbsp; &nbsp; &nbsp; &nbsp; <strong>功能介绍</strong></td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">boolean offer(E e)</td> 
>    <td style="width:361px;">插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 ，注意：空间不够时候会自主扩容</td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">E peek()</td> 
>    <td style="width:361px;">获取优先级最高（堆顶）的元素，如果为空，返回null</td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">E pool()</td> 
>    <td style="width:361px;">移除优先级最高的元素并返回，如果为空，返回null。</td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">int size()</td> 
>    <td style="width:361px;">获取有效元素个数</td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">void clear（）</td> 
>    <td style="width:361px;">清空</td> 
>   </tr> 
>   <tr> 
>    <td style="width:137px;">Boolean isEmpty()</td> 
>    <td style="width:361px;">检测堆是否为空，空返回true</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 注：如果容量小于64，按照原来的空间\*2扩容
> 
> 如果容量等于64，则按照原来空间\*1.5扩容
> 
> 如果容量超过MAX\_ARRAY\_SIZE,按照MAX\_ARRAY\_SIZE来扩容（不需要深究）

代码实现：

public void TestPriorityQueue2(){
        int[] arr = {4,1,9,2,8,0,7,3,6,5};
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
    // 否则在插入时需要不多的扩容
    // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e: arr) {
          q.offer(e);
        } 
       System.out.println(q.size()); // 打印优先级队列中有效元素个数
       System.out.println(q.peek()); // 获取优先级最高的元素
    // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
            q.poll();
            q.poll();
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素
            q.offer(0);
        System.out.println(q.peek()); // 获取优先级最高的元素
    // 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if(q.isEmpty()){
        System.out.println("优先级队列已经为空!!!");
        } 
       else{
        System.out.println("优先级队列不为空");
        }
    }

## 总结 ##

我们先得明白堆是什么？堆是一种优先级队列，可采用二叉树的形式来表达存储方式。在Java程序中，以及写好相关的类（**PriorityQueue**），可以使用。

值得一提的是：Java的集合框架中提供了2种类型的优先级队列：PriorityQueue和PriorityBlockingQueue。但由于PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

[tq02_CSDN_-C_Java_Java]: https://blog.csdn.net/nav/arch
[Link 1]: http://t.csdn.cn/UJdxH
[9efc1f98e3a04f7ba348f9fe24741977.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4ea74ca209274950ba44e79bed292360.png
[e011a9118f7c485781b0377a39e79f64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e6050bab6e864df399ad9818a4bc1570.png
[cf85f99761404ce8af483bce5d31a616.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/faf0c0399ab74ab5b3562ed48ca766a1.png
[8535c9f7233443de8216b559d27002b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c8b2e6d665014d4eb018e1f71a2cfb64.png
[e043e8601b6c4e888416604fb3b1b177.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/454b606f01894485beabc01b0dd304bd.png
[eee4f493834b46649d689701e11a0d98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/46aeac68439e492d85a4a72b1d00e50b.png
[10a2db83d3e74a868f2a9705a2e0a45f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7e93e4b712744f42aac01510317d1f65.png