数据结构：堆和二叉树

完全二叉树

完全二叉树是一种特殊的二叉树结构，所有层（除最后一层外）的节点都完全填满，且最后一层的最后一层节点尽可能从左到右连续排列。

例如：

1 / \ 2 3 / \ / 4 5 6

堆只分为小顶堆和大顶堆。

小顶堆和大顶堆

小顶堆是一种完全二叉树，每个父节点的值小于或等于其子节点的值。

1 / \ 3 2 / \ / 4 6 5 [1,3,2,4,6,5]

大顶堆也是一种完全二叉树，每个父节点的值大于或等于其子节点的值。

9 / \ 7 5 / \ / 4 6 3 [9,7,5,4,6,3]

向上调整和向下调整（单次调整）

典型的例子就是堆的尾增和首删。（尾删很容易，直接删最后一个数据）

堆的尾增：向上调整

堆的尾增操作通常指在堆的末尾插入新元素后，通过向上调整（Heapify Up）维护堆的性质。

第一步：插入元素到末尾
将新元素插入堆的最后一个位置（数组末尾），保持完全二叉树的结构。

第二步：向上比较交换
从插入位置开始，比较当前节点与其父节点的值。大顶堆时，若当前节点值大于父节点值（小顶堆则是小于），则交换两者位置，并继续向上比较，直到满足堆的性质或到达根节点。

时间复杂度：
最坏情况下需从叶子节点调整到根节点，复杂度为O(log N)。

逐步演示：

现在有小顶堆：

1 / \ 3 5 / \ / 4 8 6 [1, 3, 5, 4, 8, 6]

插入新元素：在堆末尾插入元素2

1 / \ 3 5 / \ / \ 4 8 6 2 [1, 3, 5, 4, 8, 6, 2]

向上调整，比较新节点与父节点：由于2 < 5，不满足最小堆性质，交换两者。

1 / \ 3 2 / \ / \ 4 8 6 5 [1, 3, 2, 4, 8, 6, 5]

继续判断，比较其与新的父节点：由于2 > 1，满足最小堆性质，停止交换。算法终止。

堆的首删：向下调整

堆的首删操作通常指删除堆顶元素后，通过向下调整（Heapify Down）维护堆的性质。

第一步：交换并删除堆顶元素

将堆顶元素（根节点）与堆的最后一个元素交换位置，随后删除末尾元素（原堆顶）。保持完全二叉树的结构。

第二步：向下比较交换

从新的堆顶开始，比较当前节点与其左右子节点的值。大顶堆时，若当前节点值小于较大子节点值（小顶堆则是大于），则交换两者位置，并继续向下比较，直到满足堆的性质或到达叶子节点。

时间复杂度：
最坏情况下需从根节点调整到叶子节点，复杂度为O(log N)。

逐步演示（小顶堆）

初始堆：

1 / \ 3 5 / \ / 4 8 6 [1, 3, 5, 4, 8, 6]

删除堆顶元素：

1.交换堆顶（1）与末尾元素（6）：

6 / \ 3 5 / \ 4 8 [6, 3, 5, 4, 8]

2.向下调整：
比较新堆顶（6）与左右子节点（3和5），选择较小子节点（3）。
由于6 > 3，交换两者：

3 / \ 6 5 / \ 4 8 [3, 6, 5, 4, 8]

继续调整节点6：比较其与子节点（4和8），选择较小子节点（4）。
由于6 > 4，交换两者：

3 / \ 4 5 / \ 6 8 [3, 4, 5, 6, 8]

节点6无子节点，调整终止,算法结束。

向上调整建堆

是一种将无序数组转换为堆结构的方法。其核心思想是从第二个节点开始，逐步向后调整每个子树，即反复使用上文的单次的向上调整，使其满足堆的性质（最大堆或最小堆）。

目标：大顶堆 5 / \ 3 6 / \ / \ 7 5 1 9 从3开始调整，然后是6 7 5 1 9。 3不用调整，6要调整 6 / \ 3 5 / \ / \ 7 5 1 9 7要调整 9 / \ 6 7 / \ / \ 3 5 1 5 9要调整，已经是最后一位，算法结束。

时间复杂度：

目标：大顶堆 5 / \ 3 6 / \ / \ 7 5 1 9 从6开始调整，然后是3，5。 6要调整，6和子节点1，9都比较，最终选择和9交换 5 / \ 3 9 / \ / \ 7 5 1 6 3要调整 5 / \ 7 9 / \ / \ 3 5 1 6 5要向下调整两次 9 / \ 7 6 / \ / \ 3 5 1 5 已经是第一位，算法结束。