tags:
  - DSA

DS. Heap (Priority Queue)

如果你熟悉树数据结构，你该知道，树有一个 root 根节点，根节点又有多个子节点，子节点后又相连有许多子节点，这些不同的节点一般用指针相连。

二叉树是一种特殊的树，二叉树的每个节点最多只能有 2 个子节点。而完全二叉树(complete binary tree) 是一棵特殊的二叉树。除了最后一层外，完全二叉树其余每层的节点都必须是满的，最后一层的节点必须从左往右连续填充。而堆，是一棵特殊的完全二叉树。

一般树的实现都是用指针实现，而完全二叉树由于其性质，一般使用数组来实现，因为完全二叉树的节点可以通过数组的索引定位到。使用数组而不使用指针而用数组有很多好处，除了节省了指针所带来的开销外，你还可以通过索引直接找到任意节点，时间复杂度为。

对于数组中的节点 i：

我们说了，堆是一棵特别的完全二叉树，它有一些属性。我们通过堆的属性把堆分成最小堆和最大堆。最小堆的根节点总是包含最小值，因此查找最小值非常高效（时间复杂度为）。同样的，最大堆的根节点总是包含最大值。

常见的数据结构操作包括增加、删除、查找、修改。我们用最小堆举例子。

当在堆中插入新元素时，新元素将被插入到堆的末尾（数组的最后一个位置）。然后新元素会和父节点逐步比较并上浮（和冒泡排序很类似），直到最小堆的性质被满足。因为这一操作是在树的一个 branch 上完成的，因而，插入操作的时间复杂度为，这和堆的高度是一样的。

删除操作通常发生在堆顶，因为堆顶是最小堆的最小值。删除堆顶后，将堆的最后一个元素放到堆顶位置，然后通过下沉操作恢复堆的性质。下沉的逻辑是：逐步与较小的子节点比较并交换，直到堆的性质得到满足。和插入操作一样，删除操作的时间复杂度也是。

查找堆顶元素的操作，即访问最小值（最小堆）或最大值（最大堆）。由于堆顶元素始终存储在数组的第一个位置，这一操作的时间复杂度为。

堆排序是一种基于堆的数据结构实现的排序算法。其逻辑是先将输入数据构建为最大堆，然后依次将堆顶元素（最大值）移除并存储到结果列表，同时调整剩余的堆。堆排序的时间复杂度为，空间复杂度为，因为它在原数组上进行排序，不需要额外的存储空间。

堆化是将一个普通的二叉树转换成堆结构的过程，通常通过 sift down 操作实现。对于每一个非叶子节点，从该节点开始逐步调整与子节点的关系，直到堆的性质得到满足。Heapify 的时间复杂度为，因为在堆化过程中，树的叶子节点已经满足堆的性质，无需调整。