python自己写的heap sort，很丑陋

深感自己实现的够丑陋，照着伪代码写下来的。

#http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
def heapSort(seq,count):
    #first place a in max-heap order
    heapify(seq,count)
    end=count-1
    while end > 0:
        seq[end],seq[0]=seq[0],seq[end]
        end-=1
        #put the heap back in max-heap order
        siftDown(seq,0,end)

def heapify(seq,count):
    start=count//2
    while start>=0:
        siftDown(seq,start,count-1)
        start-=1

def siftDown(seq,start,end):
    #end represents the limit of how far down the heap to sift
    root=start
    while root*2 + 1 <= end:
        child=root*2+1
        if child+1 <= end and seq[child] < seq[child+1]:
            child+=1
        if seq[root] < seq[child]:
            seq[root],seq[child]=seq[child],seq[root]
            root=child
        else:
            return

def test_heapsort():
    import random
    import copy
    ll=[random.randint(1,50) for i in range(20)]
    ll2=copy.deepcopy(ll)
    print(ll)
    heapSort(ll,len(ll))
    print("after heapSort:",ll)
    print(ll==sorted(ll2))

还是看看别人实现的吧。

__author__ = "lynn lin"
__lience__ = "MIT"
#heapq is priority queue
class sort_collection:

    def __init__(self,A=[]):
        self.data=A
        self.heapsize=len(A)

    def __left(self,i):
        return (2*i+1)

    def __right(self,i):
        return (2*i+2)

    def __parent(self,i):
        return (i-1)//2

    def __max_heapify(self,i):
        left=self.__left(i)
        right=self.__right(i)
        if left < self.heapsize and self.data[left] > self.data[i]:
            largest=left
        else:
            largest=i
        if right < self.heapsize and self.data[right] > self.data[largest]:
            largest=right
        if largest!=i:
            self.data[i],self.data[largest]=self.data[largest],self.data[i]
            self.__max_heapify(largest)

    def __min_heapify(self,i):
        left=self.__left(i)
        right=self.__right(i)
        if left < self.heapsize and self.data[left] < self.data[i]:
            smallest=left
        else:
            smallest=i
        if right < self.heapsize and self.data[right] < self.data[smallest]:
            smallest=right
        if smallest!=i:
            self.data[i],self.data[smallest]=self.data[smallest],self.data[i]
            self.__min_heapify(smallest)

    def build_max_heapify(self):
        for i in range(len(self.data)//2,-1,-1):
            self.__max_heapify(i)

    def build_min_heapify(self):
        for i in range(len(self.data)//2,-1,-1):
            self.__min__heapify(i)

    def heapsort(self,mode=1):
        #default sort order is ascending,if setting mode to 0,the sort order is descending
        if mode==1:
            self.build_max_heapify()
        else:
            self.build_min_heapify()

        length=len(self.data)
        for i in range(length-1,0,-1):
            self.data[i],self.data[0]=self.data[0],self.data[i]
            self.heapsize-=1
            if mode==1:
                self.__max_heapify(0)
            else:
                self.__min_heapify(0)

    def heap_maximum(self):
        return self.data[0]

    def heap_minimum(self):
        return self.data[0]

    def heap_extract_min(self):
        if self.heapsize < 1:
            raise Exception("heap empty")
        smallest=self.data[0]
        self.data[0]=self.data[self.heapsize-1]
        self.heapsize-=1
        self.__min_heapify(0)
        return smallest

    def heap_extract_max(self):
        if self.heapsize < 1:
            raise Exception("heap empty")
        biggest=self.data[0]
        self.data[0]=self.data[self.heapsize-1]
        self.heapsize-=1
        self.__max_heapify(0)
        return biggest

    def heap_increase_key(self,i,key):
        if key < self.data[i]:
            raise
        self.data[i]=key
        while i > 0 and self.data[self.__parent(i)] < self.data[i]:
            self.data[self.__parent(i)],self.data[i]=self.data[i],self.data[self.__parent(i)]
            i=self.__parent(i)

def test_sort_collection():
    import random
    l=[random.randint(1,50) for i in range(20)]
    ll=sort_collection(l)
    ll.build_max_heapify()
    #ll.heapsort()
    print(ll.data)
    ma=ll.heap_extract_max()
    mb=ll.heap_extract_max()
    mc=ll.heap_maximum()
    print(ma,mb,mc,sep=":")

test_sort_collection()

附赠代码 Sieve of Eratosthenes，感慨下这个网站 http://rosettacode.org 真不错。

#http://rosettacode.org/wiki/Sieve_of_Eratosthenes
def sieve_algorithm(number):
    is_prime=[False]*2+[True]*(number-1)
    for n in range(int(number**0.5+1.5)):
        if is_prime[n]:
            for i in range(n*n,number+1,n):
                is_prime[i]=False
    return [i for i , prime in enumerate(is_prime) if prime]