| 对于n个元素的关键字序列｛k1，k2，…，kn｝，当且仅当满足下列关系时称其为堆。
|
|
|
|
|
| 若将此序列对应的一维数组（即以一维数组作为序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。因此，在一个堆中，堆顶元素（即完全二叉树的根结点）必为序列中的最小元素（或最大元素），并且堆中任一棵子树也都是堆。若堆顶为最小元素，则称为小顶堆；若堆顶为最大元素，则称为大顶堆。
|
|
|
| 例如，将序列（48，37，64，96，75，12，26，54，03，33）中的元素依次放入一棵完全二叉树中，如下图（a）所示。显然，它既不是大顶堆（48<64），也不是小顶堆（48>37），调整为大顶堆后如下图（b）所示。
|
|
|
|
|
|
|
| 堆排序的基本思想是：对一组待排序记录的关键字，首先把它们按堆的定义排成一个序列（即建立初始堆），从而输出堆顶的最小关键字（对于小顶堆而言）。然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复，直到全部关键字排成有序序列为止。
|
|
|
| n个元素进行堆排序时，时间复杂度为O（nlog2n），空间复杂度为O（1）。堆排序是不稳定的排序方法。
|
|
|
