堆(heap)原理

矫情吗;* 2022-07-15 12:50 243阅读 0赞

(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质:

  • 堆中某个节点的值总是大于或小于其父节点的值;
  • 堆总是一颗完全树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆支持以下的基本操作: 支持的基本操作

  • build:建立一个空堆;
  • insert:向堆中插入一个新元素;
  • update:将新元素提升使其符合堆的性质;
  • get:获取当前堆顶元素的值;
  • delete:删除堆顶元素;
  • heapify:使删除堆顶元素的堆再次成为堆。

某些堆实现还支持其他的一些操作,如斐波那契堆支持检查一个堆中是否存在某个元素。

应用

堆排序

主条目: 堆排序

堆(通常是二叉堆)常用于排序。这种算法称作堆排序。

优先队列

主条目: 优先队列

最小堆常用于实现优先队列。

发表评论

表情:
评论列表 (有 0 条评论,243人围观)

还没有评论,来说两句吧...

相关阅读

    相关 JVM内存(heap

    堆的核心概述 > 一个JVM实例只存在一个堆内存,堆也是Java内存管理的核心区域。 > Java堆区在JVM启动的时候即被创建,其空间大小也就确定了。是JV

    相关 数据结构-heap

    堆(heap)也被称为优先队列(priority queue)。队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。而堆也是一样,在堆底插入元素,在堆顶取出

    相关 heap原理

    堆(英语:heap)是[计算机科学][Link 1]中一类特殊的[数据结构][Link 2]的统称。堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质: 堆中

    相关 (Heap)的实现

    什么是堆? 优先队列(Opriority Queue) 特殊的“队列”,取出元素的顺序是依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序。 ![waterma

    相关 JVM--Heap详解

    堆(Heap) 一个JVM实例只存在一个堆内存,堆内存的大小是可以调节的。 类加载器读取了类文件后,需要把类、方法、常变量放到堆内存中,保存所有引用类型的真是信息,以方