问答题 一组记录的关键字为(50,79,8,56,32,41,85),给出利用重建堆方法建立的初始堆(堆顶最大),并给出堆排序的过程。 【吉林大学2007二、5(4分)】
【正确答案】正确答案:结果的大根堆为:85,79,50,56,32,41,8。建堆过程可以描述如下。首先按序列顺序画n(待排序元素个数)个结点的完全二叉树。定义叶子结点已经是堆。从最后一个分支结点(下标n/2—1,第1个元素下标0)开始调堆,直至最后将第1个元素调整到符合堆的定义。结合本例说明如下:叶子56,32,41和85已经是堆,最后一个分支结点元素8不符合堆的定义,将85与8交换。元素79符合堆的定义,不需调整。元素50不符合堆的定义,沿元素大的右分支向下筛选(因为建大根堆),将85调到堆顶。将50放在原85的位置已满足堆的定义,否则还要继续向下筛选,直至满足堆的定义找到50的位置。
【答案解析】