|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 >
|
相关知识点:11个
|
|
|
|
对于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)。堆排序是不稳定的排序方法。
|
|
|