当我们把顺序表示的文件(R1,R2,…,Rn)看作为顺序二叉树时,由顺序二叉树的性质可知:记 R的右2的双亲是记录R12:R的左孩子是记录R2(21,但若2n,则R的左孩子不存在 录R(1 子是记录R21(2计),但若2计+1>n,则R的右孩子不存在 什么是堆呢?堆是一个具有这样性质的顺序二叉树,每个非终端结点(记录)的关键字大于等于它的 孩子结点的关键字。例如,图95所示的顺序二叉树就是一个堆。 显然,在一个堆中,根结点具有最大值(指关键字,下同),而且堆中任何一个结点的非空左、右子 树都是一个堆,它的根结点到任一叶子的每条路径上的结点都是递减有序的。 堆排序的基本思想是:首先把待排序的顺序表示(一维数组)的文件(R1,R2,…,R)在概念上看作 棵顺序二叉树,并将它转换成一个堆。这时,根结点具有最大值,删去根结点,然后将剩 下的结点重新调整为一个堆。反复进行下去,直到只剩下一个结点为止。 堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆。初始状态时,结点是随机排列的,需 要经过多次调整才能把它转换成一个堆,这个堆叫做初始堆。建成堆之后,交换根结点和堆 的最后一个结点的位置,相当于删去了根结点。同时,剩下的结点(除原堆中的根结点)又构成 棵顺序二叉树。这时,根结点的左、右子树显然仍都是一个堆,它们的根结点具有最大值 除上面删去的原堆中的根结点)。把这样一棵左、右子树均是堆的顺序二叉树调整为新堆,是 很容易实现的。 例如,对于图7-7所示的堆,交换根结点63和最后的结点30之后,便得到图9-6a)所示的顺序二叉 树除63之外)。现在,新的根结点是30,其左、右子树仍然都是堆。下面讨论如何把这棵二叉 树调整为一个新堆。 由于堆的根结点应该是具有最大值的结点,且已知左、右子树是堆,因此,新堆的根结点应该是 这棵二叉树的根结点,根结点的左孩子,根结点的右孩子(若存在的话)中最大的那个结点。于 是,先找出根结点的左、右孩子,比较它们的大小。将其中较大的孩子再与根结点比较大小。 如果这个孩子大于根结点,则将这个孩子上移到根结点的位置,而根结点下沉到这个孩子的 位置,即交换它们的位置。在图96a)中,根结点30的左、右孩子分别是60、59,由于60>59, 并且60~30,于是应交换根结点30和左孩子60的位置。 这时,新的根结点60的右子树没有改变,仍然是一个堆。但是,由于结点30下沉到左子树的根上 使得左子树有可能不再是堆了。按照上面所用的办法,把这棵子树调整为一个堆,显然,结 点30的左、右子树原来都是堆,30的左、右子树分别是40,45。由于40<45,并且45>30,于 是应交换结点30和右孩子45的位置。当我们把顺序表示的文件(R1，R2，…，Rn)看作为顺序二叉树时，由顺序二叉树的性质可知：记 录Ri (1<i≤n)的双亲是记录R[i 2]；R1的左孩子是记录R2i (2i≤n)，但若2i>n，则Ri的左孩子不存在； Ri的右孩子是记录R2i+1 (2i+1≤n)，但若2i+1>n，则Ri的右孩子不存在。 什么是堆呢?堆是一个具有这样性质的顺序二叉树，每个非终端结点(记录)的关键字大于等于它的 孩子结点的关键字。例如，图9-5所示的顺序二叉树就是一个堆。 显然，在一个堆中，根结点具有最大值(指关键字，下同)，而且堆中任何一个结点的非空左、右子 树都是一个堆，它的根结点到任一叶子的每条路径上的结点都是递减有序的。 堆排序的基本思想是：首先把待排序的顺序表示(一维数组)的文件(R1，R2，…，Rn )在概念上看作 一棵顺序二叉树，并将它转换成一个堆。这时，根结点具有最大值，删去根结点，然后将剩 下的结点重新调整为一个堆。反复进行下去，直到只剩下一个结点为止。 堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆。初始状态时，结点是随机排列的，需 要经过多次调整才能把它转换成一个堆，这个堆叫做初始堆。建成堆之后，交换根结点和堆 的最后一个结点的位置，相当于删去了根结点。同时，剩下的结点(除原堆中的根结点)又构成 一棵顺序二叉树。这时，根结点的左、右子树显然仍都是一个堆，它们的根结点具有最大值 (除上面删去的原堆中的根结点)。把这样一棵左、右子树均是堆的顺序二叉树调整为新堆，是 很容易实现的。 例如，对于图7-7所示的堆，交换根结点63和最后的结点30之后，便得到图9-6(a)所示的顺序二叉 树(除63之外)。现在，新的根结点是30，其左、右子树仍然都是堆。下面讨论如何把这棵二叉 树调整为一个新堆。 由于堆的根结点应该是具有最大值的结点，且已知左、右子树是堆，因此，新堆的根结点应该是 这棵二叉树的根结点，根结点的左孩子，根结点的右孩子(若存在的话)中最大的那个结点。于 是，先找出根结点的左、右孩子，比较它们的大小。将其中较大的孩子再与根结点比较大小。 如果这个孩子大于根结点，则将这个孩子上移到根结点的位置，而根结点下沉到这个孩子的 位置，即交换它们的位置。在图9-6(a)中，根结点30的左、右孩子分别是60、59，由于60>59， 并且60>30，于是应交换根结点30和左孩子60的位置。 这时，新的根结点60的右子树没有改变，仍然是一个堆。但是，由于结点30下沉到左子树的根上， 使得左子树有可能不再是堆了。按照上面所用的办法，把这棵子树调整为一个堆，显然，结 点30的左、右子树原来都是堆，30的左、右子树分别是40，45。由于40<45，并且45>30，于 是应交换结点30和右孩子45的位置