单选题
若对n个元素进行堆排序,则在初始建堆的过程中需要进行______次筛选,
A、
1
B、
[n/2]
C、
(n-1)/2
D、
n
【正确答案】
B
【答案解析】
在堆排序中,数据元素序列被看成是一个完全二叉树,每个元素的位置就是其在完全二叉树中的编号。在初建堆时,需要从最后一个中间结点开始筛选。由于该二叉树最后一个结点的编号是n,根据完全二叉树的性质,其双亲为[n/2],即最后一个中间结点的编号是[n/2]。因此初建堆时需要对n/2个中间结点进行筛选。
提交答案
关闭