python 利用list实现HeapSort（小顶堆）

class minHeap(object):

    def __init__(self,list):
        self.list = list
        self.length = len(list)

    def shiftdown(self, index):
        flag=False
        while index*2 < self.length and flag==False:
            #首先处理左子树
            if self.list[index] > self.list[index*2]:
                t = index*2
            else:
                t = index
            #再看看是否存在右子树
            if index*2+1 < self.length:
                if self.list[t] > self.list[index*2+1]:
                    t = index*2+1
            if t!=index:
                self.swap(index,t)
                index=t
            else:
                flag=1

    def swap(self,child_index,parent_index):
        temp = self.list[child_index]
        self.list[child_index] = self.list[parent_index]
        self.list[parent_index] = temp

    def built_heap(self):
        index = int(len(self.list)/2)
        while index>0:
            self.shiftdown(index) 
            index-=1

        if self.list[1] < self.list[0]:
            self.swap(1,0)

        print('[InFo]当前MinValue为：'+str(self.list[0]))
           

首先需要说明的一点就是python是含有内置模块heapq来实现堆排序的，所以对于本文所实现的这种方式不理解或者不喜欢的可以去调用内置模块来实现，本文所实现的只是为了学习算法和回顾数据结构而已，想这样的实现方式语言并不是关键，Python，Java，C等都可以实现，所以只是使用建议heapq（文档地址），当然最好还是自己能实现(嘻嘻)。

由于上浮法实现的性质无法对0节点做处理，我们这里所采取的做法是从1（list下标）开始，0最后处理。

再来测试下运行时间效率和数据量之前的关系：

if __name__=='__main__':
    list1 = [random.randint(0, 1000) for i in range(100)]
    list2 = [random.randint(0, 1000) for i in range(1000)]
    list3 = [random.randint(0, 1000) for i in range(10000)]
    list4 = [random.randint(0, 1000) for i in range(100000)]
    list5 = [random.randint(0, 1000) for i in range(1000000)]
    list6 = [random.randint(0, 1000) for i in range(10000000)]
    start = time.time()
    heap = minHeap(list1).built_heap()
    print('[InFo]100条数据找出最小值耗时:'+str(time.time()-start)+' s')
    start = time.time()
    heap2 = minHeap(list2).built_heap()
    print('[InFo]1000条数据找出最小值耗时:' + str(time.time() - start) + ' s')
    start = time.time()
    heap3 = minHeap(list3).built_heap()
    print('[InFo]10000条数据找出最小值耗时:' + str(time.time() - start) + ' s')
    start = time.time()
    heap4 = minHeap(list4).built_heap()
    print('[InFo]100000条数据找出最小值耗时:' + str(time.time() - start) + ' s')
    start = time.time()
    heap5 = minHeap(list5).built_heap()
    print('[InFo]1000000条数据找出最小值耗时:' + str(time.time() - start) + ' s')
    start = time.time()
    heap6 = minHeap(list6).built_heap()
    print('[InFo]10000000条数据找出最小值耗时:' + str(time.time() - start) + ' s')
           

数据量范围是100 -1000万数据

运行结果如下：

由于堆排序的时间复杂度为O（NlogN），好像运行的效率确实也印证了这一点。但是其实还可以深入下去了解下，推荐知乎上的一个问题（关于堆排序和快速排序的差异的讨论）https://www.zhihu.com/question/23873747，自己也是看了这个才知道，堆排序和缓存这个高速缓冲存储器有关，但这涉及到计算机组成原理的知识（有点忘了）。

另外，上述代码中是用蟒蛇中的列表这么个数据结构实现Hsort的，但是有个问题就是相对于字典和设置这样的内置数据结构，列表的处理效率就慢了很多，但是仔细一想堆排序的时间消耗主要是在子节点和父节点数据的比较上，所以在这一点上我觉得列表这么个数据结构并不会太多的影响该算法的效率（有不对的地方还请指正）。