|
|
|
首先，要认真掌握堆的定义，然后才能进一步理解建堆的算法。堆的定义为：n个关键字序列k1，k2，k3，…，kn称为堆，当且仅当该序列满足如下性质（也称堆性质）：①ki≤k2i且ki≤k2i+1或②ki≥k2i且ki≥k2i+1（1≤i≤n/2）。满足第①种情况的堆称为小根堆，满足第②种情况的堆称为大根堆。这里仅讨论第①种情况。
|
|
|
|
本质上，堆排序在排序过程中，是将顺序表中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小记录。堆排序分建堆和堆调整两个过程。
|
|
|
|
建堆过程为：堆排序的过程是一个不断从堆顶到叶子的调整过程（又称"筛选"）。从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第n/2个元素，因此筛选只需要从第n/2个元素开始。
|
|
|
|
堆调整过程为：将该完全二叉树中最后一个元素替代已输出的结点。若新的完全二叉树的根结点小于左右子树的根结点，则直接输出。反之，则比较左右子树根结点的大小。若左子树的根结点小于右子树的根结点（或右子树的根结点小于左子树的根结点），则将左子树（或右子树）的根结点与该完全二叉树的根结点进行交换。重复上述过程，调整左子树（或右子树），直至叶子结点，则新的二叉树满足堆的条件。
|
|
|
|
|
|
|
|
堆排序算法的时间复杂度为O(nlog2n)，这是一个不稳定的排序方法。
|
|
|
