堆的基本存储

news/2024/10/30 14:11:56/

一、概念及其介绍

堆(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 实例代码

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;}// 测试 MaxHeappublic static void main(String[] args) {MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);System.out.println(maxHeap.size());}
}

http://www.ppmy.cn/news/28254.html

相关文章

python多线程实现

用于线程实现的Python模块 Python线程有时称为轻量级进程&#xff0c;因为线程比进程占用的内存少得多。 线程允许一次执行多个任务。 在Python中&#xff0c;以下两个模块在一个程序中实现线程 - _thread模块threading模块 这两个模块之间的主要区别在于_thread模块将线程视…

L1-087 机工士姆斯塔迪奥

在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里&#xff0c;BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。 你需要处理这个副本其中的一个机制&#xff1a;NM 大小的地图被拆分为了 NM 个 11 的格子&#xff0c;BOSS 会选择若干行或/及若干列释放技能&#xff0c;玩家…

python中yield的使用

在 Python 中&#xff0c;yield 是一个关键字&#xff0c;它用于定义生成器函数。生成器函数是一个特殊的函数&#xff0c;可以返回一个迭代器&#xff0c;当生成器函数被调用时&#xff0c;它不会立即执行&#xff0c;而是返回一个生成器对象&#xff0c;通过迭代生成器对象可…

如何获取物体立体信息通过一个相机

大家都知道的3D 技术是通过双眼视觉差异 得到的 但是3D的深度并没有那么强 为什么眼睛看到的就那么强 这无法让我们相信这个视觉差理论是和人眼睛立体感是一个原理 这个如今3D 电影都在用的技术 是和真正的人眼立体感 不一样的 或者说是有瑕疵的 分析一下现在的立体感技术 是通…

详讲函数知识

目录 1. 函数是什么&#xff1f; 2. C语言中函数的分类&#xff1a; 2.1 库函数&#xff1a; 2.2 自定义函数 函数的基本组成&#xff1a; 3. 函数的参数 3.1 实际参数&#xff08;实参&#xff09;&#xff1a; 3.2 形式参数&#xff08;形参&#xff09;&#xff1a; …

【c++】STL1—STL初识

文章目录STL的基本概念STL六大组件STL中容器、算法、迭代器容器算法迭代器容器算法迭代器初识vector存放内置数据类型vector存放自定义数据类型容器嵌套容器c的面向对象和泛型编程思想&#xff0c;目的就是复用性的提升。 为了建立数据结构和算法的一套标准&#xff0c;诞生了S…

【计算机网络】网络层IP协议

文章目录一、认识IP协议二、IP协议头部格式三、IP地址划分1. IP地址分类2. 子网划分四、IP地址数量危机1. IP地址的数量限制2. NAT技术五、私网IP和公网IP六、路由1. 认识路由2. 路由表生成算法一、认识IP协议 IP协议是Internet Protocol&#xff08;互联网协议&#xff09;的…

TCP 的演化史-TCP 是一个过渡

TCP 诞生于 1970 年代早期&#xff0c;彼时没有分组交换网的大规模应用&#xff0c;彼时绝大多数通信都在使用电话&#xff0c;电报&#xff0c;电挂等电路交换技术。 诞生在这种环境下的技术不可能脱离时代的影响&#xff0c;如果一个孩子出生在一个父母关系冷漠的家庭&#x…