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:

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...

CodePudding user response：

There are a few issues:

• First and foremost, the algorithm states that "S is indexed from 1 to N". This is not how Python lists are indexed, since they start at index 0. So either you must translate the code so that all indexing is made one less, or (probably less work) you could add a dummy value at index 0 to your Python S list. Then the data can start at index 1. This also means that in the main program you must not print the value at index 0.

• You made a typo in the first if condition in shiftdown. You should correct H.S[2*parent - 1] to H.S[2*parent 1]

• The main program should not subtract one from len(A) -- that makes no sense. The length really is len(A).

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

CodePudding user response：

I tried the dummy value and it didn't work for me. I still ended up with a incorrect sort. Since using len(list) was throwing things off I made a variable heapsize In my BuildMaxHeap and MaxHeapify methods heapsize = len(list3)-1 and then used that variable in my if statements

if l <=heapsize and (list3[l]) > list3[i]:
        largest = l
    else:
         largest = i
    if r <= heapsize and (list3[r]) >list3[largest]:
        largest = r

I can't tell if this might be causing you a problem as well, but in my BuildMaxHeap I used a for statement and had to countdown to negative 1 to make sure it didn't miss the first element.

for i in range (int(heapsize/2),-1,-1):
        MaxHeapify(list3, i)