堆的基本存储(Java 实例代码)

堆的基本存储

一、概念及其介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值。
  • 堆总是一棵完全二叉树。

二、适用说明

堆是利用完全二叉树的结构来维护一组数据,然后进行相关操作,一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间,堆通常用于动态分配和释放程序所使用的对象。

若为优先队列的使用场景,普通数组或者顺序数组,最差情况为 O(n^2),堆这种数据结构也可以提高入队和出队的效率。

入队出队
普通数组O(1)O(n)
顺序数组O(n)O(1)
O(logn)O(log)

三、结构图示

二叉堆是一颗完全二叉树,且堆中某个节点的值总是不大于其父节点的值,该完全二叉树的深度为 k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆,如下图所示:

我们可以使用数组存储二叉堆,右边的标号是数组的索引。

假设当前元素的索引位置为 i,可以得到规律:

parent(i) = i/2(取整)
left child(i) = 2*i
right child(i) = 2*i +1

四、Java 实例代码

源码包下载:Downloadicon-default.png?t=N6B9https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-heap.zip

src/runoob/heap/MaxHeap.java 文件代码:

package runoob.heap;

/**
 * 堆定义
 */
public class MaxHeap<T> {
    private T[] data;
    private int count;
    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public MaxHeap(int capacity){
        data = (T[])new Object[capacity+1];
        count = 0;
    }
    // 返回堆中的元素个数
    public int size(){
        return count;
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return count == 0;
    }
    // 测试 MaxHeap
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        System.out.println(maxHeap.size());
    }
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/115241.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java“牵手”天猫商品快递费用API接口数据,天猫API接口申请指南

天猫平台商品快递费用接口是开放平台提供的一种API接口&#xff0c;通过调用API接口&#xff0c;开发者可以获取天猫商品的标题、价格、库存、商品快递费用&#xff0c;宝贝ID&#xff0c;发货地&#xff0c;区域ID&#xff0c;快递费用&#xff0c;月销量、总销量、库存、详情…

手把手教你写出第一个C语言程序

Hello, World! 1. 前言2. 准备知识2.1 环境2.2 文件的分类2.3 注释2.3.1 注释的作用2.3.2 注释的两种风格2.3.2.1 C语言的注释风格2.3.2.2 C的注释风格 2.3.3 VS中注释和取消注释的快捷键 3. 开始演示3.1 创建项目3.2 创建源文件3.3 写代码3.4 编译链接运行 4. 代码解释4.1 写主…

电脑组装教程分享!

案例&#xff1a;如何自己组装电脑&#xff1f; 【看到身边的小伙伴组装一台自己的电脑&#xff0c;我也想试试。但是我对电脑并不是很熟悉&#xff0c;不太了解具体的电脑组装步骤&#xff0c;求一份详细的教程&#xff01;】 电脑已经成为我们日常生活中不可或缺的一部分&a…

如何在VR头显端实现低延迟的RTSP或RTMP播放

技术背景 VR&#xff08;虚拟现实技术&#xff09;给我们带来身临其境的视觉体验&#xff0c;广泛的应用于城市规划、教育培训、工业仿真、房地产、水利电力、室内设计、文旅、军事等众多领域&#xff0c;常用的行业比如&#xff1a; 教育行业&#xff1a;VR头显可以用于教育…

自动化管理管理工具----Ansible

目录 ​编辑 一、Ansible概念 1.1特点 二、工作机制&#xff08;日常模块&#xff09; 2.1 核心程序 三、Ansible 环境安装部署 四、ansible 命令行模块 4.1command 模块 4.2shell 模块 4.3cron 模块 4.4user 模块 4.5group 模块 4.6copy模块 4.7file模块 4.8ho…

记录--vue 拉伸指令

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 前言 在我们项目开发中,经常会有布局拉伸的需求,接下来 让我们一步步用 vue指令 实现这个需求 动手开发 在线体验 codesandbox.io/s/dawn-cdn-… 常规使用 解决拉伸触发时机 既然我们使用了指令的方式…

C语言每日一练----Day(12)

本专栏为c语言练习专栏&#xff0c;适合刚刚学完c语言的初学者。本专栏每天会不定时更新&#xff0c;通过每天练习&#xff0c;进一步对c语言的重难点知识进行更深入的学习。 今日练习题关键字&#xff1a;最大连续1的个数 完全数计算 &#x1f493;博主csdn个人主页&#xff1…

【爬虫】5.6 Selenium等待HTML元素

目录 任务目标 创建Ajax网站 创建服务器程序 Selenium XX 等待 1. Selenium强制等待 2. Selenium隐性等待 3. Selenium循环等待 4. Selenium显示等待 等待方法 任务目标 在浏览器加载网页的过程中&#xff0c;网页的有些元素时常会有延迟的现象&#xff0c;在HTML元素…

实战系列(一)| Dubbo和Spring Cloud的区别,包含代码详解

目录 1. 概述2. 核心功能3. 代码示例4. 适用场景 Dubbo 和 Spring Cloud 都是微服务架构中的重要框架&#xff0c;但它们的定位和关注点不同。Dubbo 是阿里巴巴开源的一个高性能、轻量级的 RPC 框架&#xff0c;主要用于构建微服务之间的服务治理。而 Spring Cloud 是基于 Spri…

华为OD机试 - 字符串分割(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路1、根据题意&#xff1a;2、例如&#xff1a;3、解题思路&#xff1a; 五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《…

金仓数据库KingbaseES Windows版本启动时报错的问题

服务启动提示&#xff1a; 原因是使用的授权版本不对&#xff0c;导致服务总是启动不了 先卸载&#xff0c;重启&#xff0c;重新安装&#xff0c;选择下面这个授权文件 再启动开发工具&#xff0c;成功

Mybatis 里面的缓存机制

Mybatis 里面设计的二级缓存是用来提升数据的检索效率&#xff0c;避免每次数据的访问都需要去查询数据库。 一级缓存&#xff0c;是 SqlSession 级别的缓存&#xff0c;也叫本地缓存&#xff0c;因为每个用户在执行查询的时 候都需要使用 SqlSession 来执行&#xff0c; 为了避…

Redis进阶 - JVM进程缓存

原文首更地址&#xff0c;阅读效果更佳&#xff01; Redis进阶 - JVM进程缓存 | CoderMast编程桅杆https://www.codermast.com/database/redis/redis-advance-jvm-process-cache.html 传统缓存的问题 传统的缓存策略一般是请求到达 Tomcat 后&#xff0c;先查询 Redis &…

Gitlab创建一个空项目

1. 创建项目 Project slug是访问地址的后缀&#xff0c;跟前边的ProjectUrl拼在一起&#xff0c;就是此项目的首页地址&#xff1b; Visibility Level选择默认私有即可&#xff0c;选择内部或者公开&#xff0c;就会暴露代码。 勾选Readme选项&#xff0c;这样项目内默认会带…

CANalyzer panel

(1205条消息) CAPL 脚本中对信号&#xff0c;系统变量&#xff0c;环境变量的 事件响应_capl programs脚本怎么写信号运算_蚂蚁小兵的博客-CSDN博客 注意环境变量是在工程关联的dbc中创建的&#xff1b;而系统变量是在CANoe工程工具栏的”Environment”下的”System Variables”…

不可变集合、Lambda表达式、Stream流

不可变集合、Lambda表达式、Stream流 创建不可变集合 不能被修改的集合 应用场景 如果某个数据不能被修改&#xff0c;把它防御性的拷贝到不可变集合中是个很好的实践。 当集合对象被不可信的库调用时&#xff0c;不可变形式是安全的。 创建不可变集合 在List、Set、Map接口中…

DP读书:鲲鹏处理器 架构与编程(十一)鲲鹏生态软件架构 AND 硬件特定软件

鲲鹏生态软硬件构成 鲲鹏软件构成硬件特定软件1. Boot Loader2. SBSA 与 SBBR3. UEFI4. ACPI 鲲鹏软件构成 鲲鹏处理器的软件生态是一个不断发展的软件生态&#xff0c;服务器本身也具有复杂度多样性&#xff0c;经过很长时间的发展服务器硬件有不同的操作系统方案&#xff0c…

C语言递归写n的k次方

int Func(int n,int k) {if (k 0){return 1;}else if (k > 1){return n * Func(n, k - 1);;}}int main() {int i 0;int j 0;printf("请输入数n和他的k次方\n");scanf("%d %d", &i,&j);int r Func(i,j);printf("%d的%d次方 %d\n"…

解决无法远程连接MySQL服务的问题

① 设置MySQL中root用户的权限&#xff1a; [rootnginx-dev etc]# mysql -uroot -pRoot123 mysql> use mysql; mysql> GRANT ALL PRIVILEGES ON *.* TO root% IDENTIFIED BY Root123 WITH GRANT OPTION; mysql> select host,user,authentication_string from user; -…

InnoDB的Buffer

一、Buffer内存结构 MySQL 服务器启动的时候就向操作系统申请了一片连续的内存&#xff0c;默认128M&#xff0c;可通过从参数修改。 [server] innodb_buffer_pool_size 268435456 1.1 控制块 控制块包括该页所属的 表空间编号、页号、缓存页在 Buffer Pool 中的地址、链表…