什么是堆

简介

堆是一种基于二叉树的高级数据结构，因此通常被称为二叉堆。

🔍 什么是二叉堆？

二叉堆是一棵完全二叉树，并且满足堆的有序性性质。

堆通常通过数组来实现，数组中的每个元素对应二叉树中的一个节点，而节点中存储的值称为“键”。虽然也可以使用包含节点类和指针的树结构来实现堆，但使用数组通常更简单且更节省空间。

所有节点必须遵循以下两条规则进行排列：

1. 堆必须是一棵完全二叉树。
2. 节点必须满足堆的有序性性质。

常见误解

一个常见的误解是认为堆中的元素是有序的。实际上，堆中的元素并不排序；堆唯一的特性是：根据堆的类型不同，最大或最小的元素始终位于顶部（即根节点）。

此外，此处讨论的数据结构“堆”与C/C++、Pascal等语言中用于动态内存分配的“堆内存”没有任何关系。

1. 完全二叉树

完全二叉树是指每个节点最多有两个子节点，并且除叶节点所在层外，其他各层的节点都被完全填满。最后一层的节点也必须从左到右连续排列，左侧不能有空缺。这是完全二叉树与其他二叉树之间唯一的区别。

新元素的插入总是从左向右进行。当添加一个新节点时，必须确保该父节点的左子节点已被填充；如果尚未填充，则应先在左侧创建节点并插入新元素。

堆使用完全二叉树结构，以避免数组中出现空洞。请参考下图，对比完全二叉树与非完全二叉树的区别：

[]

2. 堆的性质

堆的构建依赖于“堆性质”，即通过比较父节点的键与其子节点的键来维持结构。本章将重点介绍两种堆结构：

• 最小堆（Min Heap）
• 最大堆（Max Heap）

最小堆基于最小堆性质构建，最大堆则基于最大堆性质实现。下面我们来看它们的区别。

2.1 最大堆性质：

该性质要求所有父节点的键值必须大于或等于其子节点的键值。因此，在最大堆中，根节点始终保存堆中最大的元素。若节点A有一个子节点B，则满足：

$key(A) >= key(B)$

[]

2.2 最小堆性质：

在最小堆中，所有父节点的键值小于或等于其子节点的键值。这一规则适用于所有后代节点。因此，根节点始终保存堆中最小的元素。若节点A有一个子节点B，则满足：

$key(A) <= key(B)$

[]