或 k≥k2 k,≤k2 1(i=1,2,…,Ln/2」 由于堆的这个性质中下标i和2i、2i+1的关系,恰好和完全二叉树中第i个结点和其 子树结点的序号间的关系一致,所以堆可以看作是n个结点的完全二叉树。而败者树是由参 加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶(双亲)结点中存放的是两个 子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点 0,存放比赛的全局获胜者 44.(1)堆的存储是顺序的 (2)最大值元素一定是叶子结点,在最下两层上 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2-,以它为根的二叉树的深度为h-i+1,则调用Ln/2次 筛选算法时总共进行的关键字比较次数不超过下式之值: ∑212h-0)=∑2(h-)=∑21js(2n∑j/2s4n 45.(1) 冠军 (2)树形选择排序基本思想:首先对n个待排序记录的关键字进行两两比较,从中选出 「n/2个较小者再两两比较,直到选出关键字最小的记录为止,此为一趟排序。我们将一趟 选出的关键字最小的记录称为“冠军”,而“亚军”是从与“冠军”比较失败的记录中找出 具体做法为:输出“冠军”后,将其叶子结点关键字改为“最大值”,然后从该叶子结点开 始,和其左(或右)兄弟比较,修改从叶子结点到根结点路径上各结点的关键字,则根结点 的关键字即为次小关键字。如此下去,可依次选出从小到大的全部关键字 (3)树形选择排序与直接选择排序相比较,其优点是从求第2个元素开始,从ni+1个 元素中不必进行ni次比较,只比较 Logan次,比较次数远小于直接选择排序;其缺点是 辅助储存空间大 (4)堆排序基本思想是:堆是n个元素的序列,先建堆,即先选得一个关键字最大或最 小的记录,然后与序列中最后一个记录交换,之后将序列中前n-1记录重新调整为堆(调堆 的过程称为“筛选”),再将堆顶记录和当前堆序列的最后一个记录交换,如此反复直至排序 结東。优点是在时间性能与树形选择排序属同一量级的同时,堆排序只需要一个记录大小供          + 2 +1 2 2 1 2 i i i i i i i i k k k k k k k k 或 （i=1,2,…,n/2） 由于堆的这个性质中下标 i 和 2i、2i+1 的关系，恰好和完全二叉树中第 i 个结点和其 子树结点的序号间的关系一致，所以堆可以看作是 n 个结点的完全二叉树。而败者树是由参 加比赛的 n 个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个 子结点中的败者数据，而让胜者去参加更高一级的比赛。另外，还需增加一个结点，即结点 0，存放比赛的全局获胜者。 44.（1）堆的存储是顺序的 （2）最大值元素一定是叶子结点，在最下两层上。 （3）在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下： 由于第 i 层上的结点数至多是 2 i-1 ,以它为根的二叉树的深度为 h-i+1，则调用 n/2 次 筛选算法时总共进行的关键字比较次数不超过下式之值： h i h i j n j n h j j i h i h h j i i h j 2 .2( ) 2 .( ) 2 . (2 ) / 2 4 1 1 1 1 1 1 1 1 1     − = − = − = − = − − − = − =   45.(1) (2)树形选择排序基本思想：首先对 n 个待排序记录的关键字进行两两比较，从中选出 n/2 个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟 选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出， 具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”，然后从该叶子结点开 始，和其左（或右）兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点 的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。 (3) 树形选择排序与直接选择排序相比较，其优点是从求第 2 个元素开始，从 n-i+1 个 元素中不必进行 n-i 次比较，只比较 log2n 次，比较次数远小于直接选择排序；其缺点是 辅助储存空间大。 (4) 堆排序基本思想是：堆是 n 个元素的序列，先建堆，即先选得一个关键字最大或最 小的记录，然后与序列中最后一个记录交换，之后将序列中前 n-1 记录重新调整为堆（调堆 的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序 结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供 05 23 05 71 23 16 05 72 73 71 23 94 16 05 68 16 23 16 71 23 16 68 72 73 71 23 94 16 ∞ 68 23 23 68 71 23 94 68 72 73 71 23 94 ∞ ∞ 68