實現(xiàn)了python的堆排序
利用堆的特性，實現(xiàn)了在10000個數(shù)的列表中，找出最小的10個數(shù)，并和傳統(tǒng)的冒泡排序進行了耗時比較。

from functools import wraps
import time,random
def timeer(name):
    def decorator(func):
        @wraps(func)
        def wrapper(*args,**kwargs):
            start = time.time()
            result = func(*args,**kwargs)
            end = time.time()
            print(name+'耗時:',end-start)
            return result
        return wrapper
    return decorator

class Heap:
    def __init__(self):
        self.__count = 0
        self.__arr = []

    def __len__(self):
        return self.__count

    def __str__(self):
        return  str(self.__arr)

    def insert(self,value):
        self.__arr.append(value)
        self.__count+=1

    def min_t_max(self): #利用大根堆
        for i in range(int((self.__count-1)/2),-1,-1):  #構(gòu)建大根堆
            self.__build_max_Heap(self.__count,i)
        for i in range(self.__count-1, 0, -1): #不斷縮小大根堆范圍并維護大根堆
            self.__arr[i], self.__arr[0] = self.__arr[0], self.__arr[i]
            self.__build_max_Heap(i,0)

    def __build_max_Heap(self,n,i): #構(gòu)建大根堆
        largest = i
        l = 2*i+1
        r = 2*i+2
        if l<n and self.__arr[l]>self.__arr[largest]:
            largest = l
        if r<n and self.__arr[r]>self.__arr[largest]:
            largest = r
        if largest != i:
            self.__arr[i],self.__arr[largest] = self.__arr[largest],self.__arr[i]
            self.__build_max_Heap(n,largest)

    @timeer('堆排序')
    def heap_search_min_n(self,n):   #在list中尋找n個最小的數(shù)
        temp = self.__arr.copy()
        self.__arr = temp[0:n] #維護一個n個數(shù)的大根堆
        for i in range(int((n-1)/2),-1,-1):
            self.__build_max_Heap(n,i)
        for i in temp[n:]:
            if i<self.__arr[0]:
                self.__arr[0] = i
                for i in range(int((n - 1) / 2), -1, -1):
                    self.__build_max_Heap(n, i)
        minest_list = self.__arr.copy()
        self.__arr = temp
        return minest_list

@timeer('冒泡排序')
def bubble_search_min_n(arr,n):
    count = len(arr)
    for x in range(0,count):
        for y in range(0,count-x-1):
            if arr[y] > arr[y+1]:
                arr[y],arr[y+1]=arr[y+1],arr[y]
    return arr[:n]

#堆排序?qū)崿F(xiàn)
h = Heap()
for i in range(0,10):
    h.insert(random.randint(0,10))
h.min_t_max()
print('堆排序',h)

#從10000個不相同隨機數(shù)列表中,挑出10個最小值
heap = Heap()
p = [] #防止重復(fù)
number = 10000
for  i in range(0,number):
    temp = random.randint(0,number*10)
    while temp in p:
        temp = random.randint(0,number*10)
    p.append(temp)
    heap.insert(temp)
print('堆排序',heap.heap_search_min_n(10))  #o(n)
print('冒泡排序',bubble_search_min_n(p,10))  #o(n2)

output:
堆排序 [0, 2, 3, 4, 4, 4, 6, 9, 9, 10]
堆排序耗時: 0.0020275115966796875
堆排序 [108, 79, 75, 63, 76, 42, 15, 32, 46, 60]
冒泡排序耗時: 14.59396767616272
冒泡排序 [15, 32, 42, 46, 60, 63, 75, 76, 79, 108]

可以看到，在數(shù)據(jù)量為10000的情況下，堆排序比冒泡排序快了近萬倍