二叉堆详解

本文详细介绍二叉堆的基本原理、分类及实现方式。

1. 基本原理

二叉堆是一种特殊的二叉树。能动态排序的数据结构主要有两种：二叉堆和二叉搜索树。

1.1 分类

二叉堆主要分为两类：

1. 小顶堆
2. 大顶堆

对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。

同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。

1.2 API操作

二叉堆的主要操作包括：

1. sink() - 下沉操作
2. swim() - 上浮操作
3. peek() - 查看堆顶元素

• Push 插入新元素，直接放在底层的最右节点，保持完全二叉树的特点。再通过swim()上浮到合适位置。
• Pop 删除新元素，把堆顶元素删除，把二叉树底层的最右侧元素摘除并移动到堆顶，保持完全二叉树特点。在通过sink()下沉到合适位置。

2. 实现方式

2.1 链式（麻烦）

链式实现需要通过遍历找到最底层的最右节点，实现较为复杂。

2.2 数组

数组实现可以方便地定位最底层的最右节点，是二叉堆的常用实现方式。