def min_heapify(A,k, n):
left = 2*k +1
right = 2*k +2
n=int(len(A))
if left < n and A[left] < A[k]:
smallest = left
else:
smallest = k
if right< n and A[right] < A[smallest]:
smallest = right
if smallest != k:
A[k], A[smallest] = A[smallest], A[k]
min_heapify(A, smallest, n)
def build_min_heap(A):
n = int((len(A)//2)-1)
for k in range(n, -1, -1):
min_heapify(A,k,n)
def heapsort(A):
n= int(len(A))
build_min_heap(A)
for i in range(n-1, 0, -1):
A[i], A[0] = A[0], A[i]
min_heapify(A, i, 0)
A = [8,7,9,1,4,6,3]
heapsort(A)
print(A)
The output i am getting is :[4, 3, 1, 8, 6, 9, 7] and I want the array or list to be sorted in Non increasing order, built my min_heapify, build_min_heap functions and even the heapsort function like the default pseudocode. What did I do wrong here? Please help me out
There are a couple of bugs.
First, min_heapify cannot use n=int(len(A)), it must respect the size of the heap that is passed in. Otherwise, in the second phase of the algorithm, it will heapify over the end of the array where the sorted elements are, which sort of absorbs them back into the heap.
But, first-and-a-half, when that is fixed then build_min_heap no longer builds a min-heap. That's because it passes the wrong size: it passes n, but n in that context is less than half the size of the heap. Previously the first bug would compensate for this, but no longer. Solution: pass len(A) as the size here.
Second, in the second phase of the algorithm, min_heapify(A, i, 0) has the second and third parameters switched around. Naturally, i is the size of the heap, and 0 is the index to be heapified, but they are passed the other way around: heapifying item i of a 0-size heap doesn't even make sense.
After I fixed those things, I got the right result, but I would not dare to say that the code is now bug-free, there may yet be something else lurking in the code that I did not find.