2 堆排序（Floyd Williams）.pptVIP

§ 10.4.2 堆排序（Floyd Williams） 直接选择的比较次数多是因为后一趟未利用前一趟的比较结构，树形选择可克服此缺点，但它耗费的空间大，故实用的树形选择是堆排序。 思想 将R[1..n]看作是1棵完全二叉树的顺序存储结构，利用完全二叉树的双亲和孩子之关系，在当前无序区里选择最小（大）元扩充至有序区。 二叉堆（快速选择最大/小元） n个keys序列K1, K2, …，Kn称为堆，当且仅当满足如下性质（堆性质，堆序）： （1） 或 （2） 这里， 。即i结点不是叶子 § 10.4.2 堆排序 堆性质 将R[1..n]看作是完全二叉树的顺序存储结构时，堆性质实质上是满足如下性质的完全二叉树： 树中任一非叶结点的key均不大/小于其左右孩子（若存在）结点的key。即：从根到任一叶子的路径上的结点序列是一个有序序列，堆中任一子树仍是堆。它适合查找吗？ § 10.4.2 堆排序 算法思想 1、初始化 将R[1..n]建成大根堆，即初始无序区。 2、排序 交换：设当前无序区是大根堆R[1..i]，交换其中的首尾记录，即最大元R[1]（堆顶）交换到无序区尾部（有序区头部），使有序区在R的尾部逐渐扩大： R[1..i-1].keys≤R[i..n].keys //前者为无序区，后者为有序区 显然，i＝n,n-1,…,2，即n－1趟排序即可完成。 调整：将新无序区R[1..i-1]调整为堆。注意：只有R[1]可能违反堆性质。 § 10.4.2 堆排序 算法实现 void HeapSort( SeqList R ) { int i; BuildHeap( R ); //将R[1..n]建成初始堆 for ( i=n; i1; i-- ) { //进行n-1趟堆排序，当前无序区为R[1..i] R[1] R[i]; //无序区首尾记录交换，R[0]做暂存单元 Heapify( R,1,i-1 ); //将R[1..i-1]重新调整为堆 } } 如何调整堆和构造初始堆？ § 10.4.2 堆排序 调整（重建）堆 设调整区间为R[low..high]，因为只有根R[low]违反堆序，它的两子树（若存在，则根为R[2low]，R[2low+1]）均是堆。 无须调整 若R[low].key不小于两孩子的Keys，则R[low]不违反堆序 必须调整 将R[low]和它的两孩子中较大者交换： 设R[large].key=max{ R[2low].key, R[2low+1].key } 令R[low] R[large] 交换后R[large]可能违反堆序，重复上述过程，直至被调整的结点已满足堆序，或该结点已是叶子。 § 10.4.2 堆排序 调整堆算法 void Heapify( SeqList R, int low, int high ) { int large; //只有R[low]可能违反堆序 RecType temp=R[low]; for ( large=2*low; large=high; large*=2 ) { //R[low]是当前调整结点，若largehigh，则R[low]是叶子，结束； //否则，先令large指向R[low]的左孩子 if (largehigh R[large].keyR[large+1].key ) large++; //若R[large]有右兄弟，且右兄弟大，则令large指向右兄弟 if ( temp.key=R[large].key ) break; //满足堆序 R[low]=R[large]; //交换，小的筛下 low=large; //令low指向新的调整结点 } R[low]=temp; //将被调整结点放到最终的位置 } § 10.4.2 堆排序 构造初始堆算法 将R[1..n]建成堆，须将其每个结点为根的子树均调