首页 > 编程语言 >Java中的Heap(堆)(如果想知道Java中有关堆的知识点,那么只看这一篇就足够了!)

Java中的Heap(堆)(如果想知道Java中有关堆的知识点,那么只看这一篇就足够了!)

时间:2024-07-20 19:27:07浏览次数:17  
标签:知识点 Java int 元素 usedSize elem Heap child 节点

        前言:(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)逐个插入元素

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

import java.util.Arrays;

public class MaxHeap {
    private int[] elem; // 存储堆元素的数组
    private int usedSize; // 堆中元素的数量

    // 构造函数,初始化堆的容量
    public MaxHeap(int maxSize) {
        this.elem = new int[maxSize];
        this.usedSize = 0;
    }

    // 逐个插入元素的方法
    public void offer(int val) {
        // 如果堆已满,扩展数组容量为原来的两倍
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        // 将新元素放入数组的最后一位
        elem[usedSize++] = val;
        // 进行上浮操作,保持堆的性质
        shiftUp(usedSize - 1);
    }

    // 检查堆是否已满
    private boolean isFull() {
        return usedSize == elem.length;
    }

    // 上浮操作,将新插入的元素移动到正确位置
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        // 当child不为根节点,并且父节点的值小于子节点的值时,进行交换
        while (parent >= 0) {
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    // 交换数组中的两个元素
    private void swap(int fpos, int spos) {
        int tmp = elem[fpos];
        elem[fpos] = elem[spos];
        elem[spos] = tmp;
    }

    // 主函数测试
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(6);
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(4);

        System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));
    }
}

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

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

        (2)批量建堆

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

import java.util.Arrays;

public class MaxHeap {
    private int[] elem; // 存储堆元素的数组
    private int usedSize; // 堆中元素的数量

    // 构造函数,初始化堆的容量
    public MaxHeap(int maxSize) {
        this.elem = new int[maxSize];
        this.usedSize = 0;
    }

    // 批量建堆的方法
    public void createHeap(int[] array) {
        // 将数组的每个元素插入到堆中
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }

        // 从最后一个非叶节点开始进行向下调整算法
        // 计算最后一个非叶节点的索引
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    // 下沉操作,将根节点向下移动以维持堆的性质
    private void shiftDown(int root, int len) {
        int child = 2 * root + 1; // 计算左孩子的索引
        while (child < len) {
            // 如果右孩子存在且大于左孩子,则选择右孩子
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            // 如果孩子节点大于根节点,则交换它们,并继续向下调整
            if (elem[child] > elem[root]) {
                swap(child, root);
                root = child; // 更新根节点的索引
                child = 2 * root + 1; // 计算新的左孩子索引
            } else {
                break; // 如果孩子节点不大于根节点,结束向下调整
            }
        }
    }

    // 交换数组中两个元素的位置
    private void swap(int pos1, int pos2) {
        int temp = elem[pos1]; // 临时保存第一个位置的元素
        elem[pos1] = elem[pos2]; // 将第二个位置的元素赋值到第一个位置
        elem[pos2] = temp; // 将临时保存的元素赋值到第二个位置
    }

    // 主函数用于测试
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        int[] array = {3, 1, 6, 5, 2, 4};
        maxHeap.createHeap(array);
        System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));
    }
}

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

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

4.堆的基本操作

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

(1)插入操作

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

// 插入元素的方法
    public void offer(int val) {
        // 如果堆已满,扩展数组容量为原来的两倍
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        // 将新元素放入数组的最后一位
        elem[usedSize++] = val;
        // 进行上浮操作,保持堆的性质
        shiftUp(usedSize - 1);
    }

    // 检查堆是否已满
    private boolean isFull() {
        return usedSize == elem.length;
    }

    // 向上调整算法,将新插入的元素移动到正确位置
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        // 当child不为根节点,并且父节点的值小于子节点的值时,进行交换
        while (parent >= 0) {
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

(2)删除操作

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

public void poll() {
    // 将根节点(索引0)与堆的最后一个节点交换位置
    swap(0, usedSize - 1);
    
    // 移除堆的最后一个节点(原根节点),减少堆的大小
    usedSize--;
    
    // 从根节点开始进行下沉调整,恢复堆的性质
    shiftDown(0, usedSize);
}

private void swap(int pos1, int pos2) {
    // 交换堆中两个指定位置的元素
    int temp = elem[pos1];
    elem[pos1] = elem[pos2];
    elem[pos2] = temp;
}

private void shiftDown(int root, int len) {
    int child = 2 * root + 1; // 计算左孩子的索引
    while (child < len) {
        // 如果右孩子存在且大于左孩子,则选择右孩子
        if (child + 1 < len && elem[child] < elem[child + 1]) {
            child++;
        }
        // 如果选中的孩子节点大于当前根节点,则交换并继续下沉
        if (elem[child] > elem[root]) {
            swap(child, root);
            root = child; // 更新根节点为刚刚下沉的孩子节点
            child = 2 * root + 1; // 更新孩子节点的索引
        } else {
            break; // 当前根节点已经大于或等于所有孩子节点,结束下沉
        }
    }
}

(3)返回堆顶元素

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

public boolean isEmpty() {
    // 检查堆是否为空
    // 如果堆的大小为0,则返回true,表示堆为空;否则返回false
    return usedSize == 0;
}

public int peekHeap() {
    // 查看堆顶元素
    if (isEmpty()) {
        // 如果堆为空,则抛出异常
        throw new NullElementException("优先队列中没有元素!!!");
    }
    // 返回堆顶元素(根节点)
    return elem[0];
}

(4)判断堆是否为空

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

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

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


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

标签:知识点,Java,int,元素,usedSize,elem,Heap,child,节点
From: https://blog.csdn.net/2302_80198073/article/details/140574991

相关文章

  • 自学Java第三周
    本周学习一、循环1.while循环先判断条件,符合再执行。while(){}2.dowhile循环先执行一次,再判断条件。do{}while();3.forfor(初始条件;判断条件;循环迭代语句){}4.嵌套循环各种类型的循环都可以做内外侧循环。for(){for(){......;}}for(){while(){......;}}...5.控制循环结构break:完全结束一个循环,跳出循环体。continue:结束本次循环,开始下次循......
  • Java--抽象类
    目录抽象类的概念抽象类的语法抽象类的作用抽象类的概念在面向对象的概念中,所有的对象都是通过类来描述的,但是反过来,并不是所有的类都是用来描述对象的,如果一个类中没有包含足够的信息来描绘一个具体的对象,这样的类就是抽象类。我们之前所学习的Animal类或者Shape类,就可......
  • java进阶(面向对象实例代码)
    1.抽象类和接口抽象类示例abstractclassAnimal{abstractvoidmakeSound();voidsleep(){System.out.println("Sleeping...");}}classDogextendsAnimal{@OverridevoidmakeSound(){System.out.println("Bark&......
  • 类明显存在却报 package not found, Java程序中专门被其他工程所依赖的common jar用sp
    先上官方链接:https://docs.spring.io/spring-boot/docs/2.1.0.RELEASE/maven-plugin/examples/repackage-classifier.html在使用SpringBoot构建通用JAR库时,尤其是当通springboot默认的过spring-boot-maven-plugin插件打包时。如果遇到了类存在但报“packagenotfound......
  • Java基础语法01-运算符&流程控制语句If
    Java基础语法1.运算符1.1算术运算符(理解)1.1.1运算符和表达式运算符:对常量或者变量进行操作的符号表达式:用运算符把常量或者变量连接起来符合java语法的式子就可以称为表达式。​不同运算符连接的表达式体现的是不同类型的表达式。举例说明:inta=10;intb=2......
  • Java基础语法02——While循环和Switch
    4.switch语句4.1switch语句结构(掌握)格式switch(表达式){ case1: 语句体1; break; case2: 语句体2; break; ... default: 语句体n+1; break;}执行流程:首先计算出表达式的值其次,和case依次比较,一旦有对应的值,就会执行相应的语句,在执行的过程中......
  • JAVA 基础数据类型
    一、数据类型Java语言是一个面向对象的语言,但是Java中的基本数据类型却是不面向对象的,这在实际使用时存在很多的不便,为了解决这个不足,在设计类时为每个基本数据类型设计了一个对应的类进行代表,这样八个和基本数据类型对应的类统称为包装类(WrapperClass),有些地方也翻译为外......
  • JavaScript - jSignature移动端手写签名
    <html><head><scriptsrc="https://cdn.bootcdn.net/ajax/libs/jquery/3.7.1/jquery.min.js"></script><scriptsrc="https://cdn.bootcdn.net/ajax/libs/jSignature/2.1.3/jSignature.min.js"></script>......
  • javascript条件判断语句。
    if语句条件满足就执行,不满足就不执行if(条件){语句}ifelse语句条件满足,执行语句1,条件不满足,执行语句2if(条件){语句1}else{语句2}ifelseifelseif… if(条件1){ 语句1 }else{ 语句2 }if(条件2){ 语句2 }el......
  • java的一些基础知识
    文章目录JDK、JRE、JVM变量关键字标识符规则数据类型基本数据类型(简单数据类型)引用数据类型(除基本数据类型以外的数据类型)运算符Java流程控制语句分支语句循环语句特殊的流程控制语句方法形参实参数组数组动态初始化和静态初始化数组的复制数组的扩容数组的删除二维......