python堆排序

实现了python的堆排序
利用堆的特性，实现了在10000个数的列表中，找出最小的10个数，并和传统的冒泡排序进行了耗时比较。

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):  #构建大根堆
            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): #构建大根堆
        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个最小的数
        temp = self.__arr.copy()
        self.__arr = temp[0:n] #维护一个n个数的大根堆
        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]

#堆排序实现
h = Heap()
for i in range(0,10):
    h.insert(random.randint(0,10))
h.min_t_max()
print('堆排序',h)

#从10000个不相同随机数列表中,挑出10个最小值
heap = Heap()
p = [] #防止重复
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]

可以看到，在数据量为10000的情况下，堆排序比冒泡排序快了近万倍