问答题
设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O形式给出，并给出证明。【上海交通大学2004四(10分)】
【正确答案】正确答案：堆排序的时间由建堆和反复筛选两部分时间构成。对深度为h的堆，“筛选”所需进行的关键字比较的次数至多为2(h一1)；对n个关键字，建成深度为h=[log
2
n]+1的堆，所需进行的关键字比较的次数至多为C(n)，它满足下式：
【答案解析】