• 数据结构-优先级队列(堆)

    文章目录

    目录

    文章目录

    前言

    一 . 堆

    二 . 堆的创建(以大根堆为例)

    堆的向下调整(重难点)

     堆的创建

     堆的删除

    向上调整

    堆的插入

    三 . 优先级队列

    总结

    前言

    大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列

    一 . 堆

    堆（Heap）是一种基于完全二叉树的数据结构，具有以下特点：

    1. 完全二叉树：堆是一种完全二叉树，即除了最后一层外，其他层的节点都是满的，并且最后一层的节点都靠左排列。

    2. 堆序性：堆中的每个节点都满足堆序性质，即对于最大堆（Max Heap），父节点的值大于或等于其子节点的值；对于最小堆（Min Heap），父节点的值小于或等于其子节点的值。

    堆通常用数组来实现，其中数组的索引表示节点在堆中的位置。对于一个节点在索引i的堆，其左子节点在索引2i，右子节点在索引2i+1，父节点在索引i/2。

    堆常常被用来实现优先级队列，因为它能够快速找到最大或最小的元素，并且在插入和删除操作时保持堆序性质。

    常见的堆有两种类型：

    1. 最大堆（大根堆）：父节点的值大于或等于其子节点的值。最大堆的根节点是堆中的最大元素。

    2. 最小堆（小根堆）：父节点的值小于或等于其子节点的值。最小堆的根节点是堆中的最小元素。

    堆的常见操作包括：

    1. 插入（Insertion）：将一个元素插入到堆中，需要保持堆序性质。

    2. 删除根节点（Delete Root）：删除堆中的根节点，需要调整堆以保持堆序性质。

    3. 查找最大/最小元素（Find Max/Min）：在最大堆中查找最大元素，在最小堆中查找最小元素，时间复杂度为O(1)。

    4. 堆排序（Heap Sort）：利用堆的性质进行排序，时间复杂度为O(nlogn)。

    二 . 堆的创建(以大根堆为例)

    初始化工作

    public class BigHeap {
    int[] elem; // 用来记录堆中的元素
    int size;

    public BigHeap(int capacity) {
        elem = new int[capacity];
    }
    
    //再初始化的时候默认给一个数组
    public void initHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            size++;
        }
    }

    public boolean isFull() {
        return elem.length == size;
    }

    public void swap(int i,int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

    }

    堆的向下调整(重难点)

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

    父节点的值大于或等于其子节点的值。最大堆的根节点是堆中的最大元素。

    根据层序遍历构建出的二叉树显然并不符合我们的要求,这个是时候我们就需要进行向下调整

    在最大堆中，向下调整的过程是将当前节点与其子节点中较大的节点进行比较，如果当前节点小于其中较大的子节点，就将它们交换位置。然后，继续向下比较和交换，直到当前节点不再小于其子节点或者已经到达叶子节点。

    思考一下,这个时候我们应该从哪个节点进行调整?

    我们通常是从最后一个非叶子节点开始向下调整，直到根节点或者到达叶子节点为止。从最后一个非叶子节点开始向下调整的原因是，只有非叶子节点才有子节点，而叶子节点没有子节点，所以没有必要对叶子节点进行向下调整操作。

    最后一个非叶子节点的索引可以通过公式计算得到：n/2-1，其中n是堆中元素的数量。

    步骤

    1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子,因为是完全二叉树)

    2. 如果parent的左孩子存在，即:child < len， 进行以下操作，直到parent的左孩子不存在

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

    图解

    { 27,15,19,18,28,34,65,49,25,37 }

    len: 数组的长度

    parent: 表示指向需要调整的节点指针

    child: 表示指向孩子节点的指针

    最后一个非叶子节点: 根据公式parent = (child-1)/2 在这里child表示最后一个节点的索引

    parent = (len - 1 - 1)/2 = 4 我们应该从4索引开始进行向下调整

     进行到这里左子树宣告调整完毕,开始进行右子树的调整

     调整完毕!

    代码实现

    1.     private void shiftDown(int parent, int len) {
    2.         int child = 2 * parent + 1;
    3.  
    4.         // 对交换引起的堆结构的改变进行调整(如果改变就调整)
    5.         while (child < len) {
    6.             // 找出左右孩子中最大的孩子,用child进行记录
    7.             if (child + 1 < len && elem[child] < elem[child + 1]) {
    8.                 child++;
    9.             }
    10.  
    11.             // 判断大小关系
    12.             if (elem[child] > elem[parent]) {
    13.                 swap(child,parent);
    14.  
    15.                 // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
    16.                 parent = child;
    17.                 child = 2 * parent + 1;
    18.             } else {
    19.                 // 左孩子为空,表示以最开始的parent为根的二叉树已经是大根堆结构
    20.                 break;
    21.             }
    22.         }
    23.  
    24.     }

     堆的创建

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

     堆的删除

    注意：堆的删除一定删除的是堆顶元素。具体如下：

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

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

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

    1.     public int poll(){
    2.         int temp = elem[0];
    3.         swap(0, size);
    4.         size--;
    5.         // 调整完之后需要进行先下调整,因为原来的最后一个元素变成了堆顶元素,不用想的肯定不满足大根堆的结构
    6.         shiftDown(0, size);
    7.         return temp;
    8.     }

    向上调整

    在最大堆中，向上调整的过程是将当前节点与其父节点进行比较，如果当前节点大于其父节点，就将它们交换位置。然后，继续向上比较和交换，直到当前节点不再大于其父节点或者已经到达根节点。

    1.     private void shiftUp(int child) {
    2.         while (child != 0) {
    3.             int parent = (child - 1) / 2;
    4.             if (elem[parent] < elem[child]) {
    5.                 swap(child,parent);
    6.                 child = parent;
    7.             } else {
    8.                 break;
    9.             }
    10.         }
    11.     }

    堆的插入

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

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

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

    小根堆中插入10

    1.     public void offer(int val) {
    2.         if (isFull()) {
    3.             this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
    4.         }
    5.  
    6.         elem[size] = val;
    7.         shiftUp(size);
    8.         size++;
    9.     }

     总代码

    1. public class BigHeap {
    2.     int[] elem;
    3.     int size;
    4.  
    5.     public BigHeap(int capacity) {
    6.         elem = new int[capacity];
    7.     }
    8.  
    9.     public void initHeap(int[] arr) {
    10.         for (int i = 0; i < arr.length; i++) {
    11.             elem[i] = arr[i];
    12.             size++;
    13.         }
    14.     }
    15.  
    16.     public void createHeap() {
    17.         for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
    18.             shiftDown(parent, size);
    19.         }
    20.     }
    21.  
    22.  
    23.     public int poll(){
    24.         int temp = elem[0];
    25.         swap(0, size);
    26.         size--;
    27.         // 调整完之后需要进行先下调整,因为原来的最后一个元素变成了堆顶元素,不用想的肯定不满足大根堆的结构
    28.         shiftDown(0, size);
    29.         return temp;
    30.     }
    31.  
    32.     private void shiftDown(int parent, int len) {
    33.         int child = 2 * parent + 1;
    34.  
    35.         // 对交换引起的堆结构的改变进行调整(如果改变就调整)
    36.         while (child < len) {
    37.             // 找出左右孩子中最大的孩子,用child进行记录
    38.             if (child + 1 < len && elem[child] < elem[child + 1]) {
    39.                 child++;
    40.             }
    41.  
    42.             // 判断大小关系
    43.             if (elem[child] > elem[parent]) {
    44.                 swap(child,parent);
    45.  
    46.                 // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
    47.                 parent = child;
    48.                 child = 2 * parent + 1;
    49.             } else {
    50.                 // 左孩子为空,表示以最开始的parent为根的二叉树已经是大根堆结构
    51.                 break;
    52.             }
    53.         }
    54.  
    55.     }
    56.  
    57.     public void offer(int val) {
    58.         if (isFull()) {
    59.             this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
    60.         }
    61.  
    62.         elem[size] = val;
    63.         shiftUp(size);
    64.         size++;
    65.     }
    66.  
    67.     private void shiftUp(int child) {
    68.         while (child != 0) {
    69.             int parent = (child - 1) / 2;
    70.             if (elem[parent] < elem[child]) {
    71.                 swap(child,parent);
    72.                 child = parent;
    73.             } else {
    74.                 break;
    75.             }
    76.         }
    77.     }
    78.  
    79.     public boolean isFull() {
    80.         return elem.length == size;
    81.     }
    82.  
    83.     public void swap(int i,int j){
    84.         int temp = elem[i];
    85.         elem[i] = elem[j];
    86.         elem[j] = temp;
    87.     }
    88. }

    三 . 优先级队列

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

    优先级队列可以用于很多场景，例如任务调度、进程调度、事件处理等。在任务调度中，可以根据任务的优先级来决定先执行哪些任务；在进程调度中，可以根据进程的优先级来决定先执行哪些进程；在事件处理中，可以根据事件的优先级来决定先处理哪些事件。

    在实际应用中，优先级队列可以通过使用堆来实现，因为堆具有良好的时间复杂度和空间复杂度。通过使用堆来实现优先级队列，可以在log₂ n的时间复杂度内插入和删除元素，以及在O(1)的时间复杂度内获取优先级最高的元素。

    注意点:

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

    2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常

    3. 不能插入null对象，否则会抛出NullPointerException

    4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

    5. 插入和删除元素的时间复杂度为O(log₂ n)

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

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

    堆模拟实现优先级队列

    1.     class MyPriorityQueue {
    2.         // 演示作用，不再考虑扩容部分的代码
    3.         private int[] array = new int[100];
    4.         private int size = 0;
    5.  
    6.         public void offer(int e) {
    7.             array[size++] = e;
    8.             shiftUp(size - 1);
    9.         }
    10.  
    11.         public int poll() {
    12.             int oldValue = array[0];
    13.             array[0] = array[size--];
    14.             shiftDown((size-1-1)/2,size);
    15.             return oldValue;
    16.         }
    17.  
    18.         public int peek() {
    19.             return array[0];
    20.         }
    21.     }

    总结

    这篇文章给大家重点讲解了堆的模拟实现还有其应用之一 优先级队列,大家好好理解,我们下一篇博客见。

  • 相关阅读:
    《TCP/IP详解 卷一》第11章 DNS
    Unity小组工程实践项目《最强外卖员》策划案&纠错文档
    五分钟带你了解Python基础知识【精华】
    【NAS】整机备份还原Windows/Linux系统，群晖最强套件ABB教程
    MPI学习笔记（三）：矩阵相乘的分块并行(行列划分法)
    新建并配置本地Git仓库的远程仓库--GitHub、推送本地仓库到GitHub。
    从普通进阶成优秀的测试/开发程序员，一路过关斩将
    学习与尝试 --> 事件风暴
    2023.11.6 Spring 使用注解存储 Bean 对象
    【1day】用友GRP-U8 OA slbmbygr.jsp接口SQL注入漏洞学习
  • 原文地址：https://blog.csdn.net/weixin_73869209/article/details/133579975