首页 > 一个老师提出的问题

一个老师提出的问题

堆是否是有序的?若是无序的,怎么看堆排序?它为什么叫堆排序?


堆排序不是给堆排序,而是用堆给数列排序。狭义上,堆只是部分有序。


那要看你如何定义“有序”了。以下以二叉堆来说明:
1)二叉堆中父节点总是大于等于(或小等)其任何一个子节点,从这点看,它是有序的;
2)二叉堆在存储时,方便来说用数组存,纵观整列数组A[0...N],它又是无序的。

再来说堆排序,它与堆本身是否有序并没有关系,堆排序说白了就是堆的删除操作,因为二叉堆的性质使得第一个元素A[0]必定是最大(或最小)的,每次取走A[0]元素直到整个堆为空,就完成了降序(或升序)排列了。

至于为什么要叫堆排序,额,我斗胆地揣摩下它可能是由于用了堆的性质所以叫heapsort的吧

【热门文章】
【热门文章】