[其它]数据结构10章.ppt

存储此序列的一维数组，可看成是一棵完全二叉树，则堆的定义表明：完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子的结点的值。完全二叉树的根结点(堆顶元素)必为序列中n个元素的最小值(或最大值)。在此定义下，树形选择排序就转化为堆排序。 例1： 序列：{96, 83, 27, 38, 11, 09} 38 11 96 83 27 09 (从小到大的堆) 堆顶元素最大的堆 例2： 序列：{12, 36, 24, 85, 47, 30, 53, 91} (从大到小的堆) 堆顶元素最小的堆 85 47 12 36 24 30 53 91 堆排序：若堆顶元素最小，则输出之。若输出堆顶元素之后，使得剩余n－1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。 堆排序需解决两个问题： ① 如何由一个无序序列建成一个堆？ ② 输出堆顶元素之后，如何调整剩余元素成为一个新堆？ (2)堆排序：(以堆顶元素最小为例) (3)堆排序的算法描述： 对于问题①，弗洛伊德(R.W.Floyol)给出了称为“筛选”的算法： ⅰ) n个记录的序列按层次任意构成一完全二叉树； ⅲ) 每个非终端结点与其左、右孩子比较，找出最小的作为根结点，并交换之； ⅱ) 完全二叉树的最后一个非终端结点是第?n/2?个元素，筛选只需从第?n/2?个元素开始依次往上进行； ⅳ) 如果破坏了堆的结构，则转ⅲ)，直到满足堆的结构为止。 这个算法通过逐遍的筛选，把大的关键字筛到堆底。我们还是以前面例子的序列举例说明。 例：给定8个关键字的无序序列：{49, 38, 65, 97, 76, 13, 27, 49}。为直观起见，我们用完全二叉树的形式排列(实际上是一维数组)，画出建堆过程。 97 76 49 38 65 13 27 49 49 76 49 38 65 13 27 97 1327 2765 沿左支筛下65 4997 筛下97 49 76 49 38 13 65 27 97 38494976 不筛 49 76 13 38 49 65 27 97 49 76 49 38 13 65 27 97 1338 3849 沿右支筛下49 2749 4965 沿右支筛下49 49 76 13 38 27 65 49 97 经4次筛选后，得新的层序序列： 第一个元素为最小的关键字，则输出之。 {13, 38, 27, 49, 76, 65, 49, 97} 对于问题②，重建新堆：若将第一个元素与最后一个元素交换，此时的新堆称为“大顶堆”。那么，重新对第1个至第n－1个元素(此例共7个)建新堆时，不必从第?(n－1)/2?个元素开始筛选，图中的堆为第2至第n－1个元素已满足堆的定义，因此只需将第1个元素筛选即可。下面我们来讨论筛选算法的实现。考虑一般性，我们从序列中的任何一个元素开始进行筛选。 (3) 筛选算法： P281 typedef SqList HeapType; // 堆采用顺序表存储表示void HeapAdjust(HeapType H, int s, int m) { // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足 // 堆的定义，本函数调整H.r[s]的关键字，使H.r[s..m]成 // 为一个大顶堆(对其中记录的关键字而言)。 rc = H.r[s];  for (j = 2*s; j = m; j *= 2) {  // 沿key较大的孩子结点向下筛选 if (j m LT(H.r[j].key, H.r[j+1].key)) + + j;  // j为key较大的记录的下标  if (!LT(rc.key, H.r[j].key)) break; //rc应插入在位置s上 H.r[s] = H.r[j]; s = j;  } // for H.r[s] = rc; // 插入} // HeapAdjust (4) 堆排序算法： P282 void HeapSort(HeapType H) { // 对顺序表H进行堆排序。 for (i = H.length/2; i 0; －－i)