devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java中的Heap（堆）（如果想知道Java中有关堆的知识点，那么只看这一篇就足够了！）_java 堆

作者：寸_铁 | 2024-08-20 02:44:56

赞

踩

java 堆

        前言：（Heap）是一种特殊的完全二叉树，它在诸多算法中有着广泛的应用，本文将详细介绍Java中的堆。

✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容：

目录

1.堆的初识

        堆的定义

2.堆的存储方式 + 基本结论

        （1）堆的存储方式

        （2）堆中的基本结论

3.堆的创建

        （1）逐个插入元素

        （2）批量建堆

4.堆的基本操作

（1）插入操作

（2）删除操作

（3）返回堆顶元素

（4）判断堆是否为空

1.堆的初识

        ——堆是一种特殊的完全二叉树，分为最大堆（大顶堆）和最小堆（小顶堆）。最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。

        堆常用于实现优先队列（PriorityQueue），在图算法（如Dijkstra最短路径算法和Prim最小生成树算法）中也有重要应用。（读者若有兴趣可以自行了解！）

        堆的定义

        ——堆是一种特殊的完全二叉树，满足以下两个条件：

  1. 完全二叉树：

    1. 除了最后一层，其他层的节点都是满的，并且最后一层的节点从左到右连续排列。（如图）

  1. 堆性质：

    • 最大堆：每个节点的值都大于或等于其子节点的值。

    • 最小堆：每个节点的值都小于或等于其子节点的值。

        堆的这些性质使得堆顶元素（根节点）在最大堆中是最大值，在最小堆中是最小值。这样我们就大致的了解了什么是堆了！

2.堆的存储方式 + 基本结论

        （1）堆的存储方式

        从堆的概念可知，堆是一棵完全二叉树，通常情况下，堆是通过数组来实现，因为数组可以高效地访问任意位置的元素，并且通过简单的算术操作可以找到父节点和子节点的位置。（如左图a）

        但是对于二叉树中非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低（如右图b）

        ——这样我们就知道了堆就是将链式结构的完全二叉树转换为数组形式进行存储。

        （2）堆中的基本结论

        那么了解完了堆的基本存储形式，接下来让我们看看堆中的基本结论，从上文中我们已经提及在堆中我们可以通过简单的算术操作可以找到父节点和子节点的位置，那么如何实现呢？

现在我们假设 i 为节点在数组中的下标，则有：

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

       

        ——读者可以根据上图进行自我验证！！！

这样我们就大致的了解了堆中的基本结论了。

3.堆的创建

        ——创建堆的过程可以通过两种方式实现：逐个插入元素（使用向上调整算法）和批量建堆（使用向下调整算法）。逐个插入元素的方法相对简单，但批量建堆的方法效率更高。

        （1）逐个插入元素

        这种方法通过逐个插入元素来创建堆，每次插入新元素后，使用向上调整算法操作将其移动到正确位置，以保持堆的性质。

  1. import java.util.Arrays;
  2.  
  3. public class MaxHeap {
  4.     private int[] elem; // 存储堆元素的数组
  5.     private int usedSize; // 堆中元素的数量
  6.  
  7.     // 构造函数，初始化堆的容量
  8.     public MaxHeap(int maxSize) {
  9.         this.elem = new int[maxSize];
  10.         this.usedSize = 0;
  11.     }
  12.  
  13.     // 逐个插入元素的方法
  14.     public void offer(int val) {
  15.         // 如果堆已满，扩展数组容量为原来的两倍
  16.         if (isFull()) {
  17.             elem = Arrays.copyOf(elem, 2 * elem.length);
  18.         }
  19.         // 将新元素放入数组的最后一位
  20.         elem[usedSize++] = val;
  21.         // 进行上浮操作，保持堆的性质
  22.         shiftUp(usedSize - 1);
  23.     }
  24.  
  25.     // 检查堆是否已满
  26.     private boolean isFull() {
  27.         return usedSize == elem.length;
  28.     }
  29.  
  30.     // 上浮操作，将新插入的元素移动到正确位置
  31.     private void shiftUp(int child) {
  32.         int parent = (child - 1) / 2;
  33.         // 当child不为根节点，并且父节点的值小于子节点的值时，进行交换
  34.         while (parent >= 0) {
  35.             if (elem[parent] < elem[child]) {
  36.                 swap(parent, child);
  37.                 child = parent;
  38.                 parent = (child - 1) / 2;
  39.             } else {
  40.                 break;
  41.             }
  42.         }
  43.     }
  44.  
  45.     // 交换数组中的两个元素
  46.     private void swap(int fpos, int spos) {
  47.         int tmp = elem[fpos];
  48.         elem[fpos] = elem[spos];
  49.         elem[spos] = tmp;
  50.     }
  51.  
  52.     // 主函数测试
  53.     public static void main(String[] args) {
  54.         MaxHeap maxHeap = new MaxHeap(10);
  55.         maxHeap.offer(3);
  56.         maxHeap.offer(1);
  57.         maxHeap.offer(6);
  58.         maxHeap.offer(5);
  59.         maxHeap.offer(2);
  60.         maxHeap.offer(4);
  61.  
  62.         System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));
  63.     }
  64. }

        其核心逻辑就是将一个一个数据插入到数组的最后，然后根据堆（最大堆 或 最小堆）的基本概念来创建一个堆。

        ——如上图插入一个22数据，然后根据向上调整算法来实现创建最大堆。

        （2）批量建堆

        批量建堆的方法首先将所有元素放入数组中，然后从最后一个非叶子节点开始进行向下调整算法的操作，将其调整到正确位置。

  1. import java.util.Arrays;
  2.  
  3. public class MaxHeap {
  4.     private int[] elem; // 存储堆元素的数组
  5.     private int usedSize; // 堆中元素的数量
  6.  
  7.     // 构造函数，初始化堆的容量
  8.     public MaxHeap(int maxSize) {
  9.         this.elem = new int[maxSize];
  10.         this.usedSize = 0;
  11.     }
  12.  
  13.     // 批量建堆的方法
  14.     public void createHeap(int[] array) {
  15.         // 将数组的每个元素插入到堆中
  16.         for (int i = 0; i < array.length; i++) {
  17.             elem[i] = array[i];
  18.             usedSize++;
  19.         }
  20.  
  21.         // 从最后一个非叶节点开始进行向下调整算法
  22.         // 计算最后一个非叶节点的索引
  23.         for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
  24.             shiftDown(parent, usedSize);
  25.         }
  26.     }
  27.  
  28.     // 下沉操作，将根节点向下移动以维持堆的性质
  29.     private void shiftDown(int root, int len) {
  30.         int child = 2 * root + 1; // 计算左孩子的索引
  31.         while (child < len) {
  32.             // 如果右孩子存在且大于左孩子，则选择右孩子
  33.             if (child + 1 < len && elem[child] < elem[child + 1]) {
  34.                 child++;
  35.             }
  36.             // 如果孩子节点大于根节点，则交换它们，并继续向下调整
  37.             if (elem[child] > elem[root]) {
  38.                 swap(child, root);
  39.                 root = child; // 更新根节点的索引
  40.                 child = 2 * root + 1; // 计算新的左孩子索引
  41.             } else {
  42.                 break; // 如果孩子节点不大于根节点，结束向下调整
  43.             }
  44.         }
  45.     }
  46.  
  47.     // 交换数组中两个元素的位置
  48.     private void swap(int pos1, int pos2) {
  49.         int temp = elem[pos1]; // 临时保存第一个位置的元素
  50.         elem[pos1] = elem[pos2]; // 将第二个位置的元素赋值到第一个位置
  51.         elem[pos2] = temp; // 将临时保存的元素赋值到第二个位置
  52.     }
  53.  
  54.     // 主函数用于测试
  55.     public static void main(String[] args) {
  56.         MaxHeap maxHeap = new MaxHeap(10);
  57.         int[] array = {3, 1, 6, 5, 2, 4};
  58.         maxHeap.createHeap(array);
  59.         System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));
  60.     }
  61. }

        其核心思路就是先将数据全部放入数组中，在从下往上的一个一个的建立 （最大堆 或 最小堆），直到整棵树变为 （最大堆 或 最小堆）

        这样我们就了解了堆的两种创建方式了！

4.堆的基本操作

        堆的基本操作包括插入、删除和取出堆定元素、判断堆是否为空等。现在让我们详细介绍这些操作的实现方法。

（1）插入操作

        插入操作其实就是我们在创建堆中的逐个插入元素的操作，这里再让我们回顾一下：

  1. // 插入元素的方法
  2.     public void offer(int val) {
  3.         // 如果堆已满，扩展数组容量为原来的两倍
  4.         if (isFull()) {
  5.             elem = Arrays.copyOf(elem, 2 * elem.length);
  6.         }
  7.         // 将新元素放入数组的最后一位
  8.         elem[usedSize++] = val;
  9.         // 进行上浮操作，保持堆的性质
  10.         shiftUp(usedSize - 1);
  11.     }
  12.  
  13.     // 检查堆是否已满
  14.     private boolean isFull() {
  15.         return usedSize == elem.length;
  16.     }
  17.  
  18.     // 向上调整算法，将新插入的元素移动到正确位置
  19.     private void shiftUp(int child) {
  20.         int parent = (child - 1) / 2;
  21.         // 当child不为根节点，并且父节点的值小于子节点的值时，进行交换
  22.         while (parent >= 0) {
  23.             if (elem[parent] < elem[child]) {
  24.                 swap(parent, child);
  25.                 child = parent;
  26.                 parent = (child - 1) / 2;
  27.             } else {
  28.                 break;
  29.             }
  30.         }
  31.     }

（2）删除操作

        删除操作的核心思想为：将栈顶的元素和数组最后一个元素进行交换之后，删除最后一个元素，之后再对堆进行整理（整理为最小堆或最大堆）

  1. public void poll() {
  2.     // 将根节点（索引0）与堆的最后一个节点交换位置
  3.     swap(0, usedSize - 1);
  4.     
  5.     // 移除堆的最后一个节点（原根节点），减少堆的大小
  6.     usedSize--;
  7.     
  8.     // 从根节点开始进行下沉调整，恢复堆的性质
  9.     shiftDown(0, usedSize);
  10. }
  11.  
  12. private void swap(int pos1, int pos2) {
  13.     // 交换堆中两个指定位置的元素
  14.     int temp = elem[pos1];
  15.     elem[pos1] = elem[pos2];
  16.     elem[pos2] = temp;
  17. }
  18.  
  19. private void shiftDown(int root, int len) {
  20.     int child = 2 * root + 1; // 计算左孩子的索引
  21.     while (child < len) {
  22.         // 如果右孩子存在且大于左孩子，则选择右孩子
  23.         if (child + 1 < len && elem[child] < elem[child + 1]) {
  24.             child++;
  25.         }
  26.         // 如果选中的孩子节点大于当前根节点，则交换并继续下沉
  27.         if (elem[child] > elem[root]) {
  28.             swap(child, root);
  29.             root = child; // 更新根节点为刚刚下沉的孩子节点
  30.             child = 2 * root + 1; // 更新孩子节点的索引
  31.         } else {
  32.             break; // 当前根节点已经大于或等于所有孩子节点，结束下沉
  33.         }
  34.     }
  35. }

（3）返回堆顶元素

        其核心思想为：将堆中的首元素返回

  1. public boolean isEmpty() {
  2.     // 检查堆是否为空
  3.     // 如果堆的大小为0，则返回true，表示堆为空；否则返回false
  4.     return usedSize == 0;
  5. }
  6.  
  7. public int peekHeap() {
  8.     // 查看堆顶元素
  9.     if (isEmpty()) {
  10.         // 如果堆为空，则抛出异常
  11.         throw new NullElementException("优先队列中没有元素!!!");
  12.     }
  13.     // 返回堆顶元素（根节点）
  14.     return elem[0];
  15. }

（4）判断堆是否为空

          其核心思想为：数组中有没有元素

  1. public boolean isEmpty() {
  2.     // 如果 usedSize（堆的当前大小）等于0，说明堆中没有元素，返回 true。
  3.     // 否则，返回 false，表示堆中至少有一个元素。
  4.     return usedSize == 0;
  5. }

        ——通过上面的讲解，我们就大致的了解了堆中的基本操作。

以上就是本篇文章的全部内容了~~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/1004798
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号