计算机三级数据库堆排序的选择题

来源：百度知道 编辑：UC知道 时间：2024/05/09 20:14:45
一组记录的排序码（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为
a（79，46，56，38，40，84）b（84，79，56，38，40，46）
c（84，79，56，46，40，38）d（84，56，79，40，38，46）
正确答案为b
哪位可以帮忙说一下解题过程，谢了

选B

用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。

看了下书，这是个大根堆的初始堆的建立，但我建的顺序是（84，56，79，38，40，46）.
我也准备考三级数据库的，买的书是高等教育出版社的2008年版的。《全国计算机等级考试--三级教程，数据库技术》
上面给出堆的定义：堆是一个关键码序列（K1，K2,···,Kn）,它具有如下特性 Ki<=K2i,Ki<=K2i+1,i=1,2,···，【n/2】
筛选法算法是：首先要将要排序的所有关键码放到一颗完全二叉树的各个结点中（这时的二叉树并不具备堆的特性），然后从i=【n/2】的结点从Ki开始，逐步把以K[n/2],K[n/2]-1,···为根的字数排成堆，直到以Ki为根的树排成堆，就完成了建堆的过程。
根据在网上查到的资料，我的书上所说的是小根堆的排法。你的题目是大根堆的排法，原理是一样的就是把上面 的<=改成>=就是了。