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的，但是有個問題就是相對于字典和設定這樣的内置資料結構，清單的處理效率就慢了很多，但是仔細一想堆排序的時間消耗主要是在子節點和父節點資料的比較上，是以在這一點上我覺得清單這麼個資料結構并不會太多的影響該算法的效率（有不對的地方還請指正）。