本文实例讲述了Python实现堆排序的方法。分享给大家供大家参考,具体如下:
堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlogn),像插入排序而不像合并排序,它是一种原地排序算法,除了输入数组以外只占用常数个元素空间。
堆(定义):(二叉)堆数据结构是一个数组对象,可以视为一棵完全二叉树。如果根结点的值大于(小于)其它所有结点,并且它的左右子树也满足这样的性质,那么这个堆就是大(小)根堆。
我们假设某个堆由数组A表示,A[1]为树的根,给定某个结点的下标i,其父结点、左孩子、右孩子的下标都可以计算出来:
PARENT(i):
return i/2