数据结构(9)树形结构——大顶堆、小顶堆

这篇具有很好参考价值的文章主要介绍了数据结构(9)树形结构——大顶堆、小顶堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

9.1.概述

 9.2.操作

9.2.1.插入

9.2.2.删除

9.2.3.代码实现


9.1.概述

概念:

根节点是自己所在子树中的最值完全二叉树。

根节点是所在子树的最大值,称为大顶堆。

根节点是所在子树的最小值,称为小顶堆。

堆的任何子树的根节点到子树上的任意节点,路径上的节点都是有序的,大顶堆为降序,小顶堆为升序。

此处展示一个大顶堆:

数据结构(9)树形结构——大顶堆、小顶堆

作用:

堆一般用来在大量数据中找到前N大或者前N小的数据。

存储:

一般用数组来存储堆,首先因为堆一般是从空树开始建立的,不论如何操作其一定会是一颗完全二叉树,不存在大量非叶子结点没有左右孩子的情况,所以用数组来表示不会造成内存浪费。其次堆的删除操作需要从叶节点反向向根结点方向遍历,链表结构不太好支持这种反向遍历。

 9.2.操作

9.2.1.插入

堆的插入采用尾插法,新入堆的节点挂在最后一个叶节点上,然后往上浮(交换位置)。

假设已有一颗树,是按照44、25、31、18、10的插入顺序建树的。

假设插入的是20:

数据结构(9)树形结构——大顶堆、小顶堆

 假设插入的是35:

数据结构(9)树形结构——大顶堆、小顶堆

9.2.2.删除

堆的删除操作,从叶子结点开始删除的话,直接删除即可,不会有任何影响,只有在删除非叶子结点时才要考虑进行结点间的调整,保持堆是大顶堆或者小顶堆。

堆在使用时每次弹出的都是堆顶的数据,因此删除操作都是针对堆顶元素的,此处以大顶堆的删除操作为例:

用最末尾的叶节点替换根节点,然后新的根节点与左右孩子比较是否为最大值,若不为最大值,则与参与比较的三个节点中的最大值互换位置,然后递归以上过程,出口为到达叶节点或者到达合适位置。文章来源地址https://www.toymoban.com/news/detail-462483.html

9.2.3.代码实现

package linearStructure.tree.heap;

import java.util.ArrayList;
import java.util.List;

public class MaxTopHeap {
    //存储堆的数组
    private int[] heap;
    //堆的最大存储容量
    private int maxSize;
    //当前堆的存储数量
    private int heapSize;
    public MaxTopHeap(int maxSize) {
        this.heap = new int[maxSize];
        this.maxSize = maxSize;
        this.heapSize = 0;
    }
    // 判断是否为空的方法
    public boolean isEmpty() {
        return heapSize == 0;
    }

    // 判断是否填满
    public boolean isFull() {
        return heapSize == maxSize;
    }

    // 获取堆顶的值
    public int peek() throws Exception {
        if (heapSize == 0) {
            throw new Exception("heap is empty");
        }
        return heap[0];
    }

    // 往堆中添加值
    public void insert (int value) throws Exception {
        if (heapSize == maxSize) {
            throw new Exception("head is full");
        }
        heap[heapSize] = value;
        heapSize++;
        buildMaxHeap(heap);
    }

    // 删除堆顶值
    public int poll() throws Exception {
        if (heapSize == 0) {
            throw new Exception("heap is empty");
        }
        int ans = heap[0];
        swap(heap,0,--heapSize);
        buildMaxHeap(heap);
        return ans;
    }

    // 建大顶堆
    private int[] buildMaxHeap(int[] array) {
        for (int i = (heapSize-2)/2; i >= 0; i--) {
            adjustDownToUp(array,i,heapSize);
        }
        return array;
    }

    private void adjustDownToUp(int[] array, int index, int length) {
        int temp = array[index];
        for (int i = 2*index+1; i < length; i = 2*i+1) {
            if (i < length-1 && array[i] < array[i+1]) {
                i++;
            }
            if (temp >= array[i]) {
                break;
            } else {
                array[index] = array[i];
                index = i;
            }
        }
        array[index] = temp;
    }
    // 交换元素值
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 获取所有元素
    public List<Integer> getAllElements() {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < heapSize; i++) {
            ans.add(heap[i]);
        }
        return ans;
    }
}

到了这里,关于数据结构(9)树形结构——大顶堆、小顶堆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 堆排序,以及大顶堆构造过程Java实现

    先上代码,堆排序一直是稀里糊涂的。找了视频,一看就明白了,自己动手撸了一下。 一般用数组构建一种堆的关系。在数组中 每个根节点的下标 root_index = left_child_index/2 root_index = right_child_index/2 -1;   left_child_index = 2*root_index+1; right_child_index = 2*root_index+2;   记住这个关系,

    2024年02月09日
    浏览(27)
  • LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月18日
    浏览(41)
  • LeetCode·每日一题·1851. 包含每个查询的最小区间·优先队列(小顶堆)

        离线查询:  输入的结果数组queries[]是无序的。如果我们按照输入的queries[]本身的顺序逐个查看,时间复杂度会比较高。 于是,我们将queries[]数组按照数值大小,由小到大逐个查询,这种方法称之为离线查询。 位运算:  离线查询的时候,queries[]可以按照数值大小逐个

    2024年02月16日
    浏览(48)
  • 数据结构与算法:树形查找

    左子树结点值 根结点值 右子树结点值 对二叉排序树进行中序遍历,可以得到一个递增的有序数列 原理: 对于一个给定的二叉排序树,如果要查找一个节点,可以按照以下步骤进行: 从根节点开始比较。 如果要查找的值等于当前节点的值,则找到了目标节点,返回该节点。

    2024年02月06日
    浏览(41)
  • 【数据结构】树形结构所有路径复原为链表

    目录 1. 树形结构可视化 2. 树形结构转为链表 此目标是要还原树形结构的所有路径。树形结构是一种常见的数据结构,它表示元素之间层次关系。在树形结构中,每个节点可能拥有一个或多个子节点,形成了一个分层的结构。为了还原树形结构的路径,我们需要找到从根节点

    2024年02月06日
    浏览(34)
  • Java获取树形结构数据

    目录 前言: 开发前准备: 数据库: 实体类: VO对象: 代码实现: Controller层: Service层: 运行结果: 第二种 在日常的开发或者工作需求中,我们会用到树形结构数据。树形结构是一个比较常用的数据类型,一般多用于查询包含父子类关系的数据。我们常常通过父级id和层

    2024年02月12日
    浏览(37)
  • 超大量数据,前端树形结构展示

    后端返回了50万数据,让前端一次性展示成树,之前用的ant-design-vue的tree插件,卡的死死的,经过大量实验,现发现三种树可以支持如此大数量的数据。 目录 第一种:vue-easy-tree 使用方式: 1.安装插件 2.引入插件 全局引入 组件引入 3.使用  在使用虚拟滚动时,必须设置 no

    2024年01月21日
    浏览(38)
  • c语言数据结构——树形结构之树和二叉树

    二叉树有什么用? 二叉树应用非常广泛。 在操作系统源程序中,树和森林被用来构造文件系统。我们看到的window和linux等文件管理系统都是树型结构。在编译系统中,如C编译器源代码中,二叉树的中序遍历形式被用来存放C 语言中的表达式。其次二叉树本身的应用也非常多,

    2023年04月18日
    浏览(41)
  • Java8 Stream流处理树形结构数据

    参考资料 Java8新特性-使用Stream流递归实现遍历树形结构 ID为2,6,11的Menu 是 ID为1的Menu子节点 ID为3,4,5的Menu 是 ID为2的Menu子节点 💥 注意 是下面这种写法的一种更简单的写法

    2024年02月01日
    浏览(53)
  • java返回前端树形结构数据(2种实现方式)

    0.思想 首先找到一级目录(类别),然后从一级目录(类别)递归获取所有子目录(类别),并组合成为一个“目录树” 1.普通实现:controller层传的是0层,就是一级目录层,从这里开始往下递归。 2.stream流实现: 3.实体类集合专VO类集合的工具类 入参为未知类型的实体集合

    2024年02月04日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包