本文记述了堆的基本概念和表示法。
◆ 概念
堆是一种存放多个元素的数据结构，它要求每个元素都要大于等于或小于等于另外若干特定位置的元素。堆常用完全 d 叉树（以下简称“完全树”）表示，堆中的元素与树上的节点一一对应，这样的完全树是堆有序的，也被称为 d 叉堆。当完全树的每个节点都大于等于它的所有子节点时，称该堆为大根堆，反之则称为小根堆。
◆ 表示
把堆对应的完全树按照层级顺序放入数组中，规定根节点的位置为 1。例如，含有 26 个元素的大根堆，
其完全二叉树的一种可能表示为，
圆圈代表节点，节点左上方的数字为节点在数组中的位置，下同。图中位置为 k 的节点，其父节点的位置为 ⎣k/2⎦，其子节点的位置为 2k 和 2k+1；
其完全三叉树的一种可能表示为，
位置为 k 的节点，其父节点的位置为 ⎣(k+1)/3⎦，其子节点的位置为 3k-1，3k 和 3k+1；
其完全四叉树的一种可能表示为，
位置为 k 的节点，其父节点的位置为 ⎣(k+2)/4⎦，其子节点的位置为 4k-2，4k-1，4k 和 4k+1。
可以推导出，堆的完全 d 叉树中，位置为 k 的节点，其父节点的位置为 ⎣(k + (d-2)) / d⎦，其子节点的位置为 k*d - (d-2)， k*d - (d-1), ..., k*d, k*d + 1。
◆ 操作
堆需要保持有序的状态。在大根堆中，要保持父节点大于等于子节点；在小根堆中，要保持父节点小于等于子节点。为保持这种大小关系而进行的操作有上浮和下沉两种，统称为堆的有序化操作。
上浮操作是在完全树中自底向上地交换节点和其父节点来恢复堆的顺序，直到遇到了恰当的父节点（对于大根堆，就是找到更大的父节点；对于小根堆，就是找到更小的父节点）或到顶为止。
以前述三叉堆为例，堆中的 25 号节点 B，被替换为了 a，
经过上浮操作后，堆变为了如下状态。
下沉操作是在完全树中自顶向下地交换节点和其较大子节点来恢复堆的顺序，直到遇到了恰当的子节点（对于大根堆，就是找到更小的子节点；对于小根堆，就是找到更大的子节点）或到底为止。
以前述三叉堆为例，堆中的 1 号节点 Z，被替换为了 @，
经过下沉操作后，堆变为了如下状态。
