当前位置: 首页 > news >正文

【数据结构】核心数据结构之二叉堆的原理及实现

1.大顶堆和小顶堆原理

  • 什么是堆

    • 堆(Heap)是计算机科学中一类特殊的数据结构,通常是一个可以被看作一颗完全二叉树的数组对象。

    • 完全二叉树

      • 只有最下面两层节点的度可以小于2,并且最下层的叶节点集中在靠左连续的边界

      • 只允许最后一层有空缺结点且空缺在右边,完全二叉树需保证最后一个节点之前的节点都齐全;

      • 对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1

在这里插入图片描述

  • 什么是大顶堆(最大堆)
    • 大顶堆是一种完全二叉树,其每个父节点的值都大于或等于其子节点的值,即根节点的值最大。
    • 每个节点的两个子节点顺序没做要求,和之前的二叉查找树不一样。

在这里插入图片描述

  • 什么是小顶堆(最小堆)

    • 小顶堆是一种完全二叉树,其每个父节点的值都小于或等于其子节点的值,即根节点的值最小。

    • 每个节点的两个子节点顺序没做要求,和之前的二叉查找树不一样

在这里插入图片描述

  • 存储原理

    • 一般升序采用大顶堆,降序采用小顶堆。
    • 堆是一种非线性结构,用数组来存储完全二叉树是非常节省空间的,把堆看作一个数组。
      • 方便操作,一般数组的下标0不存储,直接从1节点存储。
    • 堆其实就是利用完全二叉树的结构来维护一个数组
    • 数据下表为k的节点
      • 左子节点下标为2*k的节点。
      • 右子节点就是下表为2*k+1的节点。
      • 父节点就是下标为k/2取证的节点。
  • 公式描述一下堆的定义

    • 大顶堆:arr[k] >= arr[2k+1] && arr[k] >= arr[2k]
    • 小顶堆:arr[k] <= arr[2k+1] && arr[k] <=arr[ak]
  • 小顶堆动画效果演示

  • 往堆中插入新元素,就是往数组中从索引0或1开始依次存放数据,但是顺序需要满足堆的特性

  • 如何让堆满足:
    • 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小,根据情况交互元素位置
    • 直到找到的父节点比当前新增节点大则结束

在这里插入图片描述

2.大顶堆构编码实现

  • 大顶堆(最大堆)

    • 大顶堆是一种完全二叉树,其每个父节点的值都大于或等于其子节点的值,即根节点的值最大

在这里插入图片描述

  • 编码实现
public class Heap {//用数组存储堆中的元素private int[] items;//堆中元素的个数private int num;public Heap(int capacity) {//数组下标0不存储数据,所以容量+1this.items = new int[capacity + 1];this.num = 0;}/*** 判断堆中 items[left] 元素是否小于 items[right] 的元素*/private boolean rightBig(int left, int right) {return items[left] < items[right];}/*** 交换堆中的两个元素位置*/private void swap(int i, int j) {int temp = items[i];items[i] = items[j];items[j] = temp;}/*** 往堆中插入一个元素,默认是最后面,++num先执行,然后进行上浮判断操作*/public void insert(int value) {items[++num] = value;up(num);}/*** 使用上浮操作,新增元素后,重新堆化* 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小,根据情况交互元素位置* 直到找到的父节点比当前新增节点大则结束* <p>* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k+1 的节点* 父节点就是下标为 k/2 取整的节点*/private void up(int k) {//父节点 在数组的下标是1,下标大于1都要比较while (k > 1) {//比较 父结点 和 当前结点 大小if (rightBig(k / 2, k)) {//当前节点大,则和父节点交互位置swap(k / 2, k);}// 往上一层比较,当前节点变为父节点k = k / 2;}}/*** 删除堆中最大的元素,返回这个最大元素*/public int delMax() {int max = items[1];//交换索引 堆顶的元素(数组索引1的)和 最大索引处的元素,放到完全二叉树中最右侧的元素,方便后续变为临时根结点// 为啥不能直接删除顶部元素,因为删除后会断裂,成为森林,所以需要先交互,再删除swap(1, num);//最大索引处的元素删除掉, num--是后执行,元素个数需要减少1items[num--] = 0;//通过下浮调整堆,重新堆化down(1);return max;}/*** 使用下沉操作,堆顶和最后一个元素交换后,重新堆化* 不断比较 节点 arr[k]和对应 左节点arr[2*k] 和 右节点arr[2*k+1]的大小,如果当前结点小,则需要交换位置* 直到找到 最后一个索引节点比较完成  则结束* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k+1 的节点* 父节点就是下标为 k/2 取整的节点*/private void down(int k) {//最后一个节点下标是numwhile (2 * k <= num) {//记录当前结点的左右子结点中,较大的结点int maxIndex;if (2 * k + 1 <= num) { //2 * k + 1 <= num 是判断 确保有右节点//比较当前结点下的左右子节点哪个大if (rightBig(2 * k, 2 * k + 1)) {maxIndex = 2 * k + 1;} else {maxIndex = 2 * k;}} else {maxIndex = 2 * k;}//比较当前结点 和 较大结点的值, 如果当前节点较大则结束if (items[k] > items[maxIndex]) {break;} else {//否则往下一层比较,当前节点k索引 变换为 子节点中较大的值swap(k, maxIndex);//变换k的值k = maxIndex;}}}public static void main(String[] args) {Heap heap = new Heap(20);heap.insert(42);heap.insert(48);heap.insert(93);heap.insert(21);heap.insert(90);heap.insert(9);heap.insert(3);heap.insert(40);heap.insert(32);int top;System.out.println("输出堆:");while ((top = heap.delMax()) != 0) {System.out.print(top + " ");}}
}

在这里插入图片描述

http://www.lryc.cn/news/32264.html

相关文章:

  • Spring Cloud Alibaba+saas企业架构技术选型+架构全景业务图 + 架构典型部署方案
  • RocketMQ-03
  • 大神教你在 Linux 中查看你的时区
  • Redis持久化策略
  • 显著性检验【t-test、方差分析、ks检验】
  • 访问学者在德国访学生活衣食住行攻略
  • SQL-刷题技巧-删除重复记录
  • 基于JSP的虚拟账号交易平台
  • LeetCode201_201. 数字范围按位与
  • 一款好的风险管理软件可以做什么
  • html2canvas使用文档
  • HTML DOM 改变 CSS
  • 基于EB工具的TC3xx_MCAL配置开发01_WDG模块配置介绍
  • Activty启动到显示的过程[二]
  • ubuntu 18.04.06LST安装R4.0+版本报错及解决过程
  • 数据湖架构Hudi(五)Hudi集成Flink案例详解
  • 【Java学习笔记】9.Java 循环结构 - for, while 及 do...while
  • 【面向对象初步】之面向对象VS面向过程
  • 原型链(回顾)
  • DS内排—2-路归并排序
  • 深度账户抽象(Account Abstraction)第 3 部分:Wallet创建
  • 代码分享:面波数据快速成图
  • 常见数据结构
  • Mycat
  • Java 编写Vue组件(VueGWT的初尝试)
  • 【第二章 @RequestMapping注解(value,method,params属性),springMVC支持ant风格的路径,支持路径中的占位符】
  • QML Text详解
  • xxl-job启用https访问
  • 2023FL Studio最新中文版电子音乐、混音和母带制作DAW
  • pytorch 35 yolov5_obb项目解读+使用技巧+调优经验(提升map)