什么是二叉堆?二叉堆的插入和删除

大强大大_8951

大强大大_8951

2025-08-20

247人浏览

原创

二叉堆是一种用数组实现的完全二叉树,满足堆属性,分为最小堆和最大堆,能高效插入、删除并获取最值,时间复杂度为O(log N);其核心操作为插入时的“上浮”和删除堆顶时的“下沉”;常见应用包括优先队列、堆排序、Dijkstra与Prim算法及Top K问题。

什么是二叉堆?二叉堆的插入和删除

二叉堆本质上是一种特殊的完全二叉树,它满足堆属性:要么每个父节点的值都小于或等于其子节点(最小堆),要么每个父节点的值都大于或等于其子节点(最大堆)。在我看来,它就是一种巧妙的数据结构,能让我们高效地找到集合中的最大或最小元素,并且在添加或移除元素时也能保持这种特性。

解决方案

说起二叉堆,它其实就是用数组实现的完全二叉树。这种实现方式非常精妙,因为它省去了显式的指针,通过简单的数学计算就能找到父节点和子节点。比如,对于一个索引为

i

的节点(从0开始计数),它的左子节点在

2*i + 1

,右子节点在

2*i + 2

,而它的父节点则在

(i - 1) / 2

(向下取整)。这种结构保证了树的紧凑性,也为堆操作的高效性打下了基础。

我们通常说的二叉堆,其实有两种:最小堆(Min-Heap)和最大堆(Max-Heap)。最小堆的根节点是所有元素中最小的,且每个父节点都比它的子节点小;最大堆则相反,根节点最大,且每个父节点都比它的子节点大。这种特性让它在需要频繁获取最值,同时又不断有元素进出的场景下显得格外有用。

二叉堆的插入操作是怎样实现的?

二叉堆的插入操作,在我看来,核心思想就是“先安家,再找位”。具体来说,当你有一个新元素要加入堆时,我们第一步是把它放到堆的“最后”一个位置,也就是数组的末尾。这保证了堆的“完全二叉树”结构不会被破坏。

接着,才是真正有趣的部分:这个新来的元素可能不符合堆的属性(比如在最小堆里,它可能比它的父节点还小)。这时候,我们就需要让它“上浮”(或者叫“上滤”、“冒泡”)。这个过程就是不断地将新元素与其父节点进行比较:如果新元素比父节点更符合堆的属性(例如,在最小堆中,新元素比父节点小),就交换它们的位置。这个过程会一直重复,直到新元素到达根节点,或者它不再比父节点更符合堆的属性为止。

举个例子,假设我们有一个最小堆,要插入一个值。我们把它加到数组末尾,然后从这个位置开始,向上检查。如果新元素比父节点小,就交换;然后继续向上,直到它不再小于父节点,或者到达了堆顶。这个“上浮”操作的时间复杂度是 O(log N),因为我们每次都沿着树的高度向上移动。

二叉堆的删除操作(以删除堆顶元素为例)如何进行?

二叉堆的删除操作,尤其是删除堆顶元素(这通常是最常见的删除场景,因为堆就是为了快速获取最值),逻辑上稍微复杂一点,但同样巧妙。它的基本思路是“移花接木,再重排”。

协同养育操作系统
协同养育操作系统

协同养育操作系统(Co-Parenting OS)— 离异家庭专业协同养育支持系统。12模块覆盖接送管理、成长记忆库、孩子观察站、亲子关系粘合剂、共同挑战中心、情绪冲突观察、父母成长、成长档案馆、成长阶段引擎、风险预警、驾驶舱、被恶意攻击急救包。当用户涉及离异家庭育儿、协同养育、抚养探视、接送安排、孩子成长记录、亲子关系、离异冲突、被恶意攻击、前任矛盾等话题时触发。

下载

删除堆顶元素,我们不能直接把根节点挖掉,因为那样会留下一个空缺,而且还可能破坏完全二叉树的结构。所以,我们的做法是:把堆的最后一个元素(也就是数组的最后一个元素)挪到根节点的位置,然后把原来的根节点(现在是最后一个元素)从数组中移除。这样,我们既移除了目标元素,又保持了完全二叉树的结构。

然而,新的根节点可能不符合堆的属性(比如在最小堆里,它可能比它的子节点大)。这时候,我们就需要让它“下沉”(或者叫“下滤”、“堆化”)。这个过程是:将当前节点与其子节点进行比较,找出其中最符合堆属性的子节点(例如,在最小堆中,找出最小的子节点)。如果当前节点比这个子节点更不符合堆属性(例如,在最小堆中,当前节点比最小的子节点还大),就交换它们的位置。然后,继续对交换后的新位置重复这个过程,直到当前节点不再比其子节点更不符合堆属性,或者它已经到达了叶子节点。

这个“下沉”操作同样是 O(log N) 的时间复杂度,因为它沿着树的高度向下移动。通过这种方式,二叉堆在删除堆顶元素后,依然能高效地恢复其堆特性。

二叉堆在实际应用中有哪些常见场景?

二叉堆的应用场景非常广泛,它不仅仅是一种理论上的数据结构,在很多实际问题中都扮演着核心角色。

首先,最典型的应用就是实现优先队列。优先队列是一种抽象数据类型,它允许我们以优先级的方式访问元素,而二叉堆恰好能高效地支持这种操作:插入元素(O(log N))和取出最高优先级元素(O(1) 获取,O(log N) 删除)。在操作系统中,任务调度器常常用优先队列来决定哪个任务应该先执行;在模拟系统中,事件队列也常用它来管理事件的发生顺序。

其次,堆排序(Heap Sort)是另一种基于二叉堆的经典排序算法。它利用堆的特性,先将所有元素构建成一个堆,然后重复地取出堆顶元素(最大或最小),并将其放到数组的末尾,最终实现排序。堆排序是一种原地排序算法,时间复杂度稳定在 O(N log N),在一些对内存要求严格的场景下很有优势。

再者,在图算法中,二叉堆也大放异彩。比如著名的迪杰斯特拉(Dijkstra)算法用于寻找最短路径,以及普利姆(Prim)算法用于寻找最小生成树,它们都可以利用优先队列(底层用二叉堆实现)来高效地选择下一个要处理的顶点或边,从而显著优化算法的性能。

最后,在一些数据流或大数据场景下,二叉堆也常用于解决“Top K”问题,也就是从海量数据中找出最大或最小的 K 个元素。我们可以维护一个大小为 K 的最小堆(如果找最大的 K 个),遍历数据流,如果当前元素比堆顶元素大,就替换堆顶并重新堆化。这样,堆中始终维护着当前最大的 K 个元素,而空间复杂度仅为 O(K)。这比把所有数据都加载到内存中再排序要高效得多。

总的来说,二叉堆的这些特性让它成为计算机科学中一个非常实用且高效的工具。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

操作系统

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
数据类型有哪几种
数据类型有哪几种

数据类型有整型、浮点型、字符型、字符串型、布尔型、数组、结构体和枚举等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2023.10.31

3631

5

php数据类型
php数据类型

本专题整合了php数据类型相关内容,阅读专题下面的文章了解更多详细内容。

2025.10.31

574

9

c语言 数据类型
c语言 数据类型

本专题整合了c语言数据类型相关内容,阅读专题下面的文章了解更多详细内容。

2026.02.12

622

19

sort排序函数用法
sort排序函数用法

sort排序函数的用法:1、对列表进行排序,默认情况下,sort函数按升序排序,因此最终输出的结果是按从小到大的顺序排列的;2、对元组进行排序,默认情况下,sort函数按元素的大小进行排序,因此最终输出的结果是按从小到大的顺序排列的;3、对字典进行排序,由于字典是无序的,因此排序后的结果仍然是原来的字典,使用一个lambda表达式作为key参数的值,用于指定排序的依据。

2023.09.04

1158

7

C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

2026.04.23

399

31

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2981

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Postman安装指南
Postman安装指南

共0课时 | 0人学习

Docker Desktop设置与维护手册
Docker Desktop设置与维护手册

共0课时 | 0人学习

Valgrind支持平台说明
Valgrind支持平台说明

共0课时 | 0人学习