pythonalgorithmsortingheapsort

Heapsort Implementation Python


I'm having some issues implementing HeapSort in python. Input sequence does not get properly sorted... The

implementation looks like this:

class Heap:
  def __init__(self, S, heapsize):
    self.S = S
    self.heapsize = heapsize



def shiftdown(H, i):
    
    siftkey = H.S[i]
    parent = i 
    spotfound = False

    

    while (2*parent <= H.heapsize and not spotfound):
        if (2*parent < H.heapsize and H.S[2*parent] < H.S[2*parent - 1]):
            largerchild =  2*parent + 1
        else:
            largerchild =  2*parent

        if(siftkey < H.S[largerchild]):
            H.S[parent] = H.S[largerchild]
            parent = largerchild
        else:
            spotfound = True
        
    H.S[parent] = siftkey
    



def makeheap(n, H):
    i = int(n/2)
    
    H.heapsize = n
    while i >= 1:
        shiftdown(H, i)
        i -= 1


def root(H):
    keytype = H.S[1]
    H.S[1] = H.S[H.heapsize]
    H.heapsize = H.heapsize - 1
    shiftdown(H, 1)
    return keytype

def removekeys(n, H ,A):
    
    i = n
    while(i >= 1):
        A[i] = root(H)
        i -= 1

        


def HeapSort(n, H):
    makeheap(n, H)
    removekeys(n, H, H.S)
    



if __name__ == '__main__':
    A = [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
    n = len(A) - 1

    H = Heap(A, n)
    print(H.heapsize)
    print(A)
    HeapSort(n, H)

    
    print(H.S)

The input A results in the output [30, 11, 16, 12, 14, 17, 18, 19, 20, 25]. The implementation is based on algorithm 7.5 from the book Foundations of Algorithms: Neapolitan, Richard fifth edition, and i've tried to do a direct conversion to python. Se pitchurs below.

Any suggestions would be helpful!

The algorithm from the book looks like this:

enter image description here

enter image description here

enter image description here

I've tried to go through the algorithm on pen and paper to find where the hiccup happens, but still can't seem to figure it out...


Solution

  • There are a few issues:

    Here is the corrected script:

    class Heap:
        def __init__(self, S, heapsize):
            self.S = [None] + S   # The source aglorithm has no 0 index
            self.heapsize = heapsize
    
    def shiftdown(H, i):
        siftkey = H.S[i]
        parent = i 
        spotfound = False
        while (2*parent <= H.heapsize and not spotfound):
            # bug fix
            if (2*parent < H.heapsize and H.S[2*parent] < H.S[2*parent + 1]):
                largerchild =  2*parent + 1
            else:
                largerchild =  2*parent
            if(siftkey < H.S[largerchild]):
                H.S[parent] = H.S[largerchild]
                parent = largerchild
            else:
                spotfound = True
        H.S[parent] = siftkey
        
    def makeheap(n, H):
        i = int(n/2)
        H.heapsize = n
        while i >= 1:
            shiftdown(H, i)
            i -= 1
    
    def root(H):
        keytype = H.S[1]
        H.S[1] = H.S[H.heapsize]
        H.heapsize = H.heapsize - 1
        shiftdown(H, 1)
        return keytype
    
    def removekeys(n, H ,A):    
        i = n
        while(i >= 1):
            A[i] = root(H)
            i -= 1
    
    def HeapSort(n, H):
        makeheap(n, H)
        removekeys(n, H, H.S)
    
    
    A = [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
    n = len(A) # Don't subtract one here!
    H = Heap(A, n)
    print(H.heapsize)
    print(A)
    HeapSort(n, H)
    print(H.S[1:])  # Must skip index 0