堆排序(Heap Sort)只需要一个记录大小的辅助空间
堆排序在最坏的情况下，其时间复杂度为O(nlog n),相对于快速排序来说，这是堆的最大优点。
堆是一棵完全二叉树，且树中不存在大于（小于）父节点的节点。
堆中的第i个元素大于或等于第2i个元素和第2i+1个元素。
自底向上的堆化
fixUp(Item* a, int k)
...{
while(k>1 && less(a[k/2], a[k]))
...{ exch(a[k], a[k/2]); k = k / 2; //向上找到父结点
}
}自顶向下的堆化
fixDown(Item* a, int k, int N)...{ int j; while(2*k <= N) ...{ j = 2 * k; if(j<N && less(a[j], a[j+1])) j++; //选择两个孩子中较大者，与a[k]比较 if(!less(a[k], a[j])) break; //局部满足堆条件，立即退出 exch(a[k], a[j]); //否则，交换 k = j; }}堆排序
void heapsort(Item* a, int l, int r)...{ int k, N = r-l+1; //N为待排元素的个数 for(k = N/2; k >= 1; k--) //建堆，从第一个非叶子节点开始 fixDown(a, k, N); //自顶向下的堆化 while(N > 1) ...{ exch(a[l], a[l+N-1]); //把第一个元素（最大）和最后一个元素交换 fixDown(a, 1, --N); //再自顶向下堆化 }}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
