堆（数据结构）

在最大堆中，父节点的键不小于孩子的键；沿每条向下路径重复这个关系，便能保证根节点保存最大键。最小堆把比较方向反过来。兄弟之间并不因此排好顺序，同一层也不必成为有序列表。

二叉堆还采用完全二叉树的形状，逐层填满，并把最后一层靠左放置。若数组从下标1存根，位置k的父节点在向下取整的k/2，两个孩子在2k和2k+1，因而能用下标计算关系而不逐节点保存链接。

参考：[1]

插入新元素可以先放到数组末尾，再把大于父节点的新键逐次向上交换，直到最大堆的堆序恢复。这样保留完全树形状，同时只沿一条祖先路径调整。

移除最大项时，把最后一个元素移到根，再与较大的孩子比较并向下交换，直到合适位置。每条路径的长度是对数级；若底层数组也需要扩容，额外搬移应另作摊还分析，不能当作一次比较交换就结束。

参考：[1]

如果已有一整批元素，不必逐个插入才能建堆。由较低的内部节点开始向上逐一执行下沉，每次先利用已经成为堆的孩子子树，可以在线性总时间内建立二叉堆；直接连续插入则有不同的总成本界。

堆的保证还依赖键的比较保持有效。若外部直接改动已经入堆对象的优先级，却不通知结构重新调整，根节点就可能不再是真正的最大值。它通常用于实现优先队列，与运行时把某片内存称为“堆”的存储区域概念也需分别理解。

参考：[1]