二叉堆
介绍
二叉堆是一种特殊的完全二叉树数据结构,它满足堆属性。完全二叉树是指除了最后一层外,其他层的节点都是满的,而最后一层的节点都靠左排列。二叉堆主要有两种类型:
- 最大堆:每个父节点的值都大于或等于其子节点的值
- 最小堆:每个父节点的值都小于或等于其子节点的值
二叉堆的这种特殊结构使得它可以高效地找到最大值或最小值,所以也常被用来实现优先队列。
核心特性
- 完全二叉树结构:除最底层外,每层都填满,且最底层从左到右填充
- 堆序性质:
- 最大堆:父节点值 ≥ 子节点值
- 最小堆:父节点值 ≤ 子节点值
- 高效的顶部元素访问:可以在O(1)时间内获取最大/最小元素
- 数组表示:虽然概念上是树结构,但通常用数组实现,这样可以节省指针开销并提高内存局部性
基本操作
插入元素(Insert)
向堆中添加一个新元素:
...