堆 Heap

数据结构 · 用数组装的完全二叉树（大顶堆）

什么是堆

堆还是一棵完全二叉树（从上到下、从左到右挨个填满，不留空），但它的规矩和 BST 不同：大顶堆要求每个父节点都 ≥ 它的孩子，所以堆顶永远是最大值。它不比较左右大小，只管父子。

最妙的是它不用指针、直接用一个数组装：下标 i 的左孩子是 2i+1、右孩子 2i+2、父亲是 ⌊(i-1)/2⌋。下面上下两个视图是同一个堆——上面是数组、下面是树。输入一个数插入，看它从末尾上浮到该去的位置。

插入会先放到数组末尾（树的最后一个叶子），再一路和父亲比：比父亲大就交换、上浮，直到不再比父亲大。「弹出堆顶」则相反：取走最大的根，把末尾元素搬到根上，再和较大的孩子比、下沉归位。两步都只走一条到根的路径，所以是 O(log n)。这正是优先队列和堆排序的核心。

堆在哪里用

栈、队列、数组、链表、树、堆都讲完了，剩下两种更「跳跃」的结构——哈希表和图。