筛选法建堆的问题.

来源:百度知道 编辑:UC知道 时间:2024/06/22 10:54:26
设有关键码序列(72,73,71,23,94,16,05,68),用筛选法建堆的结果为()
答案为(05,23,16,68,94,72,71,73)

想知道为什么,还想知道筛选法是什么.
谢谢

堆排序定义
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
注意: 堆中任一子树亦是堆。

Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆,在R[1]与R[i]交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆。因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆性质,以R[low]为根的树已是堆,无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质,或者该结点已是叶子为止。上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来。因此,有人将此方法称为"筛选法"。

题目的答案应该是 大根堆排序,首先你要按照给出的关键字序列 建立初始堆,此时是无序的,