python实现的堆排序算法代码详解编程语言

python实现的堆排序算法代码

def heapSort(a):  
    def sift(start, count):  
        root = start  
    
        while root * 2 + 1 < count:  
            child = root * 2 + 1  
            if child < count - 1 and a[child] < a[child + 1]:  
                child += 1  
            if a[root] < a[child]:  
                a[root], a[child] = a[child], a[root]  
                root = child  
            else:  
                return  
    
    count = len(a)  
    start = count / 2 - 1  
    end = count - 1  
    
    while start >= 0:  
        sift(start, count)  
        start -= 1  
    
    while end > 0:  
        a[end], a[0] = a[0], a[end]  
        sift(0, end)  
        end -= 1  
    
a = [-8,0,1,3,11,35,68]  
heapSort(a)  
print a # [-8, 0, 1, 3, 11, 35, 68] 
 

Recursive sift(and more readable IMHO) Version:

def heapsort(a):  
    
    def swap(a,i,j):  
        tmp = a[i]  
        a[i] = a[j]  
        a[j] = tmp    
            
    def siftdown(a, i, size):  
        l = 2*i+1  
        r = 2*i+2  
        largest = i  
        if l <= size-1 and a[l] > a[i]:  
            largest = l  
        if r <= size-1 and a[r] > a[largest]:  
            largest = r  
        if largest != i:  
            swap(a, i, largest)  
            siftdown(a, largest, size)  
                
    def heapify(a, size):  
        p = (size/2)-1  
        while p>=0:  
            siftdown(a, p, size)  
            p -= 1  
                
    size = len(a)          
    heapify(a, size)  
    end = size-1  
    while(end > 0):  
        swap(a, 0, end)  
        siftdown(a, 0, end)  
        end -= 1