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