§10.4.2堆排序(Floyd&Williams) S10.4.2堆排序 直接选绎的比较次数多是因为后一越未利用前一蜡的 童堆性质 比较结构，制形选择可克服此缺点，但它耗费的空间大， 将R[1.]看作是完全二叉树的顺序存储结构时，堆性质 故实用的树形选择是堆排序， 实质上是满足如下性质的完全二叉树： 一思想 树中任一非叶结点的ky均不大I小于其左右孩子（若存 将[1.看作是1裸完全二叉树的顺序存储结构，利用 在)结点的ky。即：从振到任一叶子的路径上的结点序列是 完全二叉树的双亲和孩子之关暴，在当前无序区里选择量 二个有序序列，维中任字树仍是堆。它适合童战具】 小（大）元扩充至有序区。 ■二叉堆（快速选择量大小元） 101556253070 705630251510 n个keys序列K1,K,K称为堆，当且仅当满足如 10 堆项 70 堆顶 下性质（维性质，堆序）： w(好 skizkzi 或 (2)1k,≥k2+1 3070 25 15 10 这里，1i≤l2.即结点不是叶子 小操维 大根 510.4.2堆排序 S10.4.2堆排序 ■算法思想 ■算法实现 1初始化将R1n建成大根堆，即初始无序区。 void HeapSort(SeqList R){ 2,韩序 inti; ◆交换：设当前无序区是大根堆R[1】,交换其中的首尾记录， BuildHeap(R方将RI.n毫成初始维 即量大元R)(堆项)交换到无序区儿部（有序区头都），使 有序区在R的具都逐新扩大： for(n;>1:i-)(进行-4随堆排序当前无序区为R1.司 R1.i-1】.keys≤R0.n可.key5前衡为无序区，后南为有序区 R[1们兰R叮：凭序区首尾记录交换，R0做言存单元 显然，i=n,n-1,2,即n一1热排序即可完成。 Heapify(R,1,i-1)方1将R1.-们置新调蓝为绳 ◆澜整：将新无序区R1-1]调整为堆，注意：只有R1)可能违 反堆性质。 ◆ 如何调整堆和构造初始堆？ 510.4.2堆排序 S10.4.2堆排序 调遵（量建）堆 ·调盖维算法 c骨程黑内8到注反维床它幽两子内 void Heapify(SeqList R,int low,int high ) int large;只有Rlow个可能连反堆序 ◆无须调量若RfIowJ.key不小于两孩子的Key5,测Row]不速反堆序 RecType temp=R[low]; ◆必演调睡将R[Ow和它的两球子中较大青交换： for large=2"low;large<=high;large"=2){ R[large].key=max(R[2low].key,R[2low+1].key Ro是当前调童结点，若arge>high,则Ro是时子，射来 ◆Rflow]→R[arge 香测，先冷arge指向Row的左孩于 交换后Rrge可能速反堆序，量复上述过程，直至被调整的纳点已满足 if (large<high &R[large].key<R[large+1].key 堆序，或该轴点已是叶子， large+;谐Rarg南右兄第，且右兄第大，则arge指向右兄 f(temp.key>=R[larg.key)break:满层撞序 Rlow=R[large]:度换，小的薄下 Iow=arge;喻low指向断的调整结点 Row小=temp;将被调睡结点放到曼簧的位重 10 1510 1510 11 1 § 10.4.2 堆排序（Floyd &Williams） 直接选择的比较次数多是因为后一趟未利用前一趟的 比较结构，树形选择可克服此缺点，但它耗费的空间大， 故实用的树形选择是堆排序。 „ 思想 将R[1..n]看作是1棵完全二叉树的顺序存储结构，利用 完全二叉树的双亲和孩子之关系，在当前无序区里选择最 小（大）元扩充至有序区。 „ 二叉堆（快速选择最大/小元） n个keys序列K1, K2, …，Kn称为堆，当且仅当满足如 下性质（堆性质，堆序）： （1） 或（2） 这里， 。即i结点不是叶子 i i i i k k k k 2 2 1 { ≥ ≥ + i i i i k k k k 2 2 1 { ≤ ≤ + 1≤i≤⎣ ⎦ n/2 2 § 10.4.2 堆排序 „ 堆性质 将R[1..n]看作是完全二叉树的顺序存储结构时，堆性质 实质上是满足如下性质的完全二叉树： 树中任一非叶结点的key均不大/小于其左右孩子（若存 在）结点的key。即：从根到任一叶子的路径上的结点序列是 一个有序序列，堆中任一子树仍是堆。它适合查找吗？ 70 56 30 25 15 10 70 10 56 25 30 15 堆顶 10 15 56 25 30 70 10 70 15 25 56 30 堆顶 小根堆 大根堆 3 § 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]可能违 反堆性质。 4 § 10.4.2 堆排序 „ 算法实现 void HeapSort( SeqList R ) { int i; BuildHeap( R ); //将R[1..n]建成初始堆 for ( i=n; i>1; i-- ) { //进行n-1趟堆排序，当前无序区为R[1..i] R[1] R[i]; //无序区首尾记录交换，R[0]做暂存单元 Heapify( R,1,i-1 ); //将R[1..i-1]重新调整为堆 } } „ 如何调整堆和构造初始堆？ 5 § 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]可能违反堆序，重复上述过程，直至被调整的结点已满足 堆序，或该结点已是叶子。 20 10 56 25 30 15 56 10 25 20 30 15 56 10 20 25 30 15 6 § 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]是当前调整结点，若large>high，则R[low]是叶子，结束； //否则，先令large指向R[low]的左孩子 if (large<high && R[large].key<R[large+1].key ) large++; //若R[large]有右兄弟，且右兄弟大，则令large指向右兄弟 if ( temp.key>=R[large].key ) break; //满足堆序 R[low]=R[large]; //交换，小的筛下 low=large; //令low指向新的调整结点 } R[low]=temp; //将被调整结点放到最终的位置 }