首页 > 编程语言 >Java——堆

Java——堆

时间:2024-09-08 15:25:44浏览次数:12  
标签:Java parent int usedSize elem child public

目录

一、什么是堆

九月在老家是收割水稻的月份,每次打完水稻,农民伯伯就会拿稻杆累成一堆。我觉得这个稻杆堆和数据结构 外形有点相似哈。
在这里插入图片描述堆是一棵完全二叉树, 但是这个完全二叉树要满足条件:其中任意一个结点要 >= 其左孩子结点和有孩子结点,这叫大根堆;其中任意一个结点要 <= 其左孩子结点和有孩子结点,这叫小根堆。
堆的逻辑结构是一棵完全二叉树,但是其所有的元素是按完全二叉树的层序存储在一个一维数组当中的(物理结构是一维数组)。
在这里插入图片描述

二、堆的存储方式

堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储。对于非完全二叉树,则不适合使用顺序方式进行存储。
在这里插入图片描述
那么对于存储到数组中的堆,也要会还原成二叉树。
对于数组中的下标i

  • 如果i=0,则i表示为根节点,否则i结点的双亲为(i-1)/ 2
  • 对于i,如果 i * 2 + 1 小于数组的长度,则i的左孩子为 i * 2 + 1,否则无左孩子。
  • 对于i,如果 i * 2 + 2 小于数组的长度,则i的右孩子为 i * 2 + 2,否则无右孩子。

三、堆的创建

堆的创建有两种方式:向下调整和向上调整。

向下调整

对于一个不是堆的任意一个数组,采用向下调整为大根堆 我们可以这样做:
先调整最下面的每一层子二叉树变大根堆,再一层一层往上面调整,那么整棵树到最后也就变为大根堆了。

  • 1.先找到最后一个根结点 (叫child结点),再找child的父节点(叫parent 结点)。
  • 2.比较父结点与 左右孩子结点中最大的孩子结点的大小,如果大于最大孩子结点则不交换,小于则交换两结点 parent=child,child=child*2+1 同时child 要在数组有效数据的范围内。
  • parent - -,重复2,parent要在数组范围内。
    在这里插入图片描述
    代码
public class TestHeap {
	//堆存在一维数组elem中
    public int[] elem;
    //堆中的元素个数
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    
    //先初始化数组
    public void  initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

	//创建堆
    public void createHeap() {
    //先调整最下面的每一层子二叉树变大根堆,再一层一层往上面调整。
        for (int parent = (elem.length-1-1)/2; parent >= 0 ;parent--) {
        
            siftDown(parent,this.usedSize);
        }

    }
//向下调整
    private void siftDown(int parent, int usedSize) {
    
        int child = parent*2+1;
        //求出左右孩子中最大的孩子
        while(child<usedSize) {
            if(child+1<usedSize && elem[child]<elem[child+1]) {
                child++;
            }
            
            if(elem[child]>elem[parent]) {
                //大于就交换
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                
                //再看下其孩子树是否要交换
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }

    }
    //打印elem数组
        public void printElem() {
        System.out.println(Arrays.toString(elem));
    }

    public static void main(String[] args) {
        int[] arr = {27,15,19,18,28,34,65,49,25,37};
        TestHeap heap = new TestHeap();
        heap.initElem(arr);
        heap.createHeap();
        heap.printElem();

    }
   }

如果想要得到小根堆,就只需求得左右孩子最小,在与父结点相比,如果父结点大则交换,否则不交换。

向上调整

因为向上调整是堆的插入的一个步骤,所以在后面写到。

四、堆的时间复杂度

向下调整建堆的时间复杂度为O(n)。向下调整建堆也是一般常用的建堆方法。
在这里插入图片描述
向上调整建堆的时间复杂度为O(n*log n )
在这里插入图片描述

五、堆的插入与删除

堆的插入:

    1. 先将元素插入到数组的后面(二叉树的最后一个元素),如果数组空间不够,则需扩容。
    1. 将最后新插入的节点向上调整,直到满足堆的性质。

在这里插入图片描述
向上调整为大根堆我们可以这样做:

  • 1.先找到最后一个根结点 (叫child结点),再找child的父节点(叫parent 结点)。
  • 2.比较父结点与 左右孩子结点中最大的孩子结点的大小,如果大于最大孩子结点则不交换,小于则交换两结点 child = parent,parent=(parent-1)/2 同时child 要>0。
//插入数据
public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[this.usedSize] = val;
        siftUp(usedSize);
        this.usedSize++;
    }
//向上调整
    private void siftUp(int usedSize) {
        int child = usedSize;
        int parent = (usedSize-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (parent-1)/2;
            }else {
                break;
            }

        }



    }
//判断数组是否满
    private boolean isFull() {

        return usedSize==elem.length;
    }

如果想让向上调整一个不是堆结构的数组为堆,就要一个一个数据的插入。
向上调整也可以调整为小根堆的。

堆的删除
堆的删除一定删除的是堆顶元素。
具体如下:

  1. 将堆顶元素对堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整
    在这里插入图片描述
    在这里插入图片描述

常见习题

1.下列关键字序列为堆的是:()
A: 100,60,70,50,32,65
B: 60,70,65,50,32,100
C: 65,100,70,32,50,60
D: 70,65,100,32,50,60

2.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,在此过程中,关键字之间的比较次数是()
A: 1 B: 2 C: 3 D: 4

3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是()
A: [3,2,5,7,4,6,8]
B: [2,3,5,7,4,6,8]
C: [2,3,4,5,7,8,6]
D: [2,3,4,5,6,7,8]

[参考答案]
1.A
2.C
在这里插入图片描述
3.C

完整代码

package Tree;

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    public void  initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }
    
    public void createHeap() {
        for (int parent = (elem.length-1-1)/2; parent >= 0 ;parent--) {
            siftDown(parent,this.usedSize);
        }

    }

    //向下调整
    private void siftDown(int parent, int usedSize) {

        int child = parent*2+1;
        while(child<usedSize) {
            if(child+1<usedSize && elem[child]<elem[child+1]) {
                child++;
            }
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * child + 1;
            }else {
                break;
            }
        }

    }
 
    //简单打印数组
    public void printElem() {
        System.out.println(Arrays.toString(elem));
    }

   //插入元素
    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[this.usedSize] = val;
        siftUp(usedSize);
        this.usedSize++;
    }
    //向上调整
    private void siftUp(int usedSize) {
        int child = usedSize;
        int parent = (usedSize-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (parent-1)/2;
            }else {
                break;
            }
        }

    }

    public boolean isFull() {

        return usedSize==elem.length;
    }
    //出堆头元素
    public int poll() {
        if(isEmpty()) {
            return -1;// 抛出异常
        }
        int tmp = elem[usedSize-1];
        elem[usedSize-1] = elem[0];
        elem[0] = tmp;
        usedSize--;
        siftDown(0,usedSize);
        return tmp;
    }

    public boolean isEmpty() {

        return usedSize==0;
    }
    //取堆头元素
    public int peek() {
        if(isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    public static void main(String[] args) {
        int[] arr = {27,49,65,25,37,34,19,18,15,28};
        TestHeap heap = new TestHeap();
        heap.initElem(arr);
        heap.createHeap();
        heap.printElem();
        //80入堆
        heap.push(80);
        heap.printElem();
        //80出堆
        heap.poll();
        heap.printElem();
    }
    
}

标签:Java,parent,int,usedSize,elem,child,public
From: https://blog.csdn.net/m0_74100417/article/details/142022000

相关文章

  • Spire.Doc for Java Version:12.9
    Spire.DocforJavaisaprofessionalWordAPIthatempowersJavaapplicationstocreate,convert,manipulateandprintWorddocumentswithoutdependencyonMicrosoftWord.Byusingthismultifunctionallibrary,developersareabletoprocesscopioustasks......
  • 代码随想录算法训练营第九天 | Javascript | 力扣Leetcode | 手撕KMP的一天 | 28. 找
    目录前言简介题目链接:28.找出字符串中第一个匹配项的下标题目链接:459.重复的子字符串前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄弱。......
  • 2024-2025年最值得选的Java毕业设计选题大全推荐:热门选题
    一、前言......
  • Spire.PDF for Java Version:10.9.0
    Spire.PDFforJavaisaPDFAPIthatenablesJavaapplicationstoread,writeandsavePDFdocumentswithoutusingAdobeAcrobat.UsingthisJavaPDFcomponent,developersandprogrammerscanimplementrichcapabilitiestocreatePDFfilesfromscratchor......
  • 1-1java语法规范
    Java语法规范java是面向对象的编程语言,一个java程序可以认为是一系列对象的集合,而这些对象通过调用彼此的方法来协同工作。下面简要介绍一下类,对象,方法和实例变量的概念。对象:对象是类的一个实例,有状态和行为。例如,一条狗是一个对象,它的状态有:颜色,名字,品种;行为有:摇尾巴,叫,吃等......
  • 1-2Java基本数据类型
    Java基本数据类型变量就是申请内存来存储值。也就是说,当创建变量的时候,需要在内存中申请空间。内存管理系统根据变量的类型为变量分配存储空间,分配的空间只能用来储存该类型数据。因此,通过定义不同类型的变量,可以在内存中储存整数、小数或者字符。Java的两大数据类型:内置......
  • 基于JavaWeb在线文件管理系统的设计与实现-计算机毕业设计源码+LW文档
    摘 要在当今信息时代,随着数字化和网络化的发展,文件管理成为各个领域中不可或缺的一部分。企业、学校、个人等各类组织和用户都需要有效地组织、存储和分享大量的电子文件。传统的文件管理方式已经不能满足快速发展的需求,因此,基于JavaWeb的在线文件管理系统的开发成为迫切需要的......
  • Java大学生实战项目-基于SpringBoot+vue 的民宿在线预定平台
    博主介绍:✌Java徐师兄、7年大厂程序员经历。全网粉丝13w+、csdn博客专家、掘金/华为云等平台优质作者、专注于Java技术领域和毕业项目实战✌......
  • Java大学生实战项目- 基于SpringBoot+vue 的在线远程考试系统
    博主介绍:✌Java徐师兄、7年大厂程序员经历。全网粉丝13w+、csdn博客专家、掘金/华为云等平台优质作者、专注于Java技术领域和毕业项目实战✌......
  • Java计算机毕业设计医生诊疗系统(开题报告+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在医疗资源日益紧张与患者需求日益增长的双重背景下,传统医疗模式面临着诸多挑战,如就诊流程繁琐、信息孤岛现象严重、医患沟通不畅等。随着信息技术的......