问答题
回答问题：
问答题
设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走找到的最小关键字后，是否还需要对于n一1个关键字从头开始建堆?为什么?
【正确答案】正确答案：不需要。因为建堆后R[1]到R[n]是堆，将R[1]与R[n]交换后，R[2]到R[n—1]仍是堆，故对R[1]到R[n一1]只需从R[1]往下筛选即可。
【答案解析】
问答题
假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施?堆排序完成后，heap中保存了关键字值的升序排列还是降序排列?【山东工业大学1996三、3(8分)】
【正确答案】正确答案：堆是n个元素的序列，堆可以看作是n个结点的完全二叉树。而树形排序是n个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时，利用堆本身就可以存放输出的有序数据，只需要一个供交换用的记录大小的辅助空间。排序后，heap数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。
【答案解析】