Heap Sort: how to sort?

Question

I'm trying to implement Heap Sort in Python, but I can't seem to get it right. I've tried to implement this pseudo code, but my code does not sort! It just sifts to ridiculous effect. I'm inclined to think that the problem is in this line:

swap the root(maximum value) of the heap with the last element of the heap

How do I get the maximum value?

That is what I have:

def my_heap_sort(sqc):                    
    def heapify(count):                
        start = (count-2)/2            
        while start >= 0:              
            sift_down(start, count-1)  
            start -= 1                 

    def swap(i, j):                    
        sqc[i], sqc[j] = sqc[j], sqc[i]

    def sift_down(start, end):         
        root = start                   

        while (root * 2 + 1) <= end:   
            child = root * 2 + 1       
            temp = root                
            if sqc[temp] < sqc[child]: 
                temp = child+1         
            if temp != root:           
                swap(root, temp)       
                root = temp            
            else:                      
                return                 

    count = len(sqc)                   
    heapify(count)                     

    end = count-1                      

    while end > 0:                     
        swap(end, 0)                   
        end -= 1                       
        sift_down(0, end)              

And I found an example with almost the same problem:

def heap_sort_example(a):                                 
    def heapify(a):                                       
        start = (len(a) - 2) / 2                          
        start -= 1                                        

    def sift_down(a, start, end):                         
        root = start                                      
        while root * 2 + 1 <= end:                        
            child = root * 2 + 1                          
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1                                
            if child <= end and a[root] < a[child]:       
                a[root], a[child] = a[child], a[root]     
                root = child                              
            else:                                         
                return                                    

    heapify(a)                                            
    end = len(a) - 1                                      
    while end > 0:                                        
        a[end], a[0] = a[0], a[end]                       
        sift_down(a, 0, end-1)                            
        end -= 1                                          

The results are different, but both are ridiculous:

>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]

>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]

Answer 1

How do I get the maximum value? You don't need to "get" it. The root is exactly the maximum, that's a defined property of a heap.

If you feel tough to understand heap sort, this chapter will be extremely helpful.

---

I rewrote your code:

def swap(i, j):                    
    sqc[i], sqc[j] = sqc[j], sqc[i] 

def heapify(end,i):   
    l=2 * i + 1  
    r=2 * (i + 1)   
    max=i   
    if l < end and sqc[i] < sqc[l]:   
        max = l   
    if r < end and sqc[max] < sqc[r]:   
        max = r   
    if max != i:   
        swap(i, max)   
        heapify(end, max)   

def heap_sort():     
    end = len(sqc)   
    start = end // 2 - 1 # use // instead of /
    for i in range(start, -1, -1):   
        heapify(end, i)   
    for i in range(end-1, 0, -1):   
        swap(i, 0)   
        heapify(i, 0)   

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)

It gives:

[-2, 1, 2, 3, 5, 7, 56]  

Answer 2

If you have push and pop, or are using built-in heapq lib, try documented solution:

from heapq import heappush, heappop
def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]