Referring to MIT's open course ware algo course chapter 4, I created heap sort according to the psuedocode given:
def heap_sort(A):
build_max_heap(A)
curr_heap_size = len(A)
while curr_heap_size:
A[0],A[curr_heap_size-1] = A[curr_heap_size-1],A
curr_heap_size -= 1
max_heapify(A,0)
return A
build_max_heap is guaranteed to be correct, as I checked it with pythons heapq library.
However, heap_sort does not seem to work correctly,
test_array = [1,5,3,6,49,2,4,5,6]
heap_sort(test_array)
print(test_array) # --> [6,5,5,4,3,49,6,2,1]
Completely stumped here, I cross checked with Heap sort Python implementation and it appears to be the same...
Would appreciate help, thank you!
EDIT: Code for max_heapify and build_max_heap:
def max_heapify(A,i):
heap_size = len(A)
l,r = i*2+1,i*2+2
largest = l
if l < heap_size and A[l] > A[largest]:
largest = l
if r < heap_size and A[r] > A[largest]:
largest = r
if largest != i:
A[i],A[largest] = A[largest],A[i]
max_heapify(A,largest)
def build_max_heap(A):
array_size = len(A)
for i in range(array_size // 2 ,-1,-1):
max_heapify(A,largest)
You have a few mistakes in your code that made it harder to regenerate your case, and find the solution to your particular issue, but here it goes.
First, your code includes a syntax error in heap_sort function, specifically when you try to swap the first and the last elements of A. On the right hand side of that assignment, the second value is A, even though it should be A[0].
Secondly, your usage of variable largest in build_max_heap implies either that largest is a global variable declaration of which you did not provide in your question, or you meant to use i, instead. I assumed it was the second case, and since I have a working heap_sort based on the code you provided, I reckon my assumption was correct.
Third, in max_heapify, you initialize largest to l, even though you should initialize it with i. I believe you will find this to be a trivial mistake, as further down that same function, you clearly expect the value of largest to be equal to that of i.
Finally, your most crucial error is that you keep passing down the entire array and use an array length that never decreases.(i.e. it is always the initial length of test_array) The algorithm you use finds the maximum element of the given array and exclude it from the remainder of the structure. That way, you have an array that keeps on decreasing in size while sending its largest element to the end.(i.e. just beyond its reach/length) But, since you never decrease the size of the array, and its length is continually computed as len(test_array), it will never work as expected.
There are two approaches that can solve your issue. Option 1 is passing down to max_heapify a shorter version of A in heap_sort. Specifically you should pass A[:curr_heap_size] at each iteration of the loop. This method can work, but it is not really space efficient, as you make a new list each time. Instead, you can pass down curr_heap_size as an argument to functions build_max_heap and max_heapify, and assume that to be the length. (i.e. as opposed to len(A))
Below is a working heap_sort implementation, based on your code. All I did was fixing the mistakes I listed above.
def max_heapify(A, heap_size, i):
l,r = i*2+1,i*2+2
largest = i
if l < heap_size and A[l] > A[largest]:
largest = l
if r < heap_size and A[r] > A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, heap_size, largest)
def build_max_heap(A, array_size):
for i in range(array_size // 2 ,-1,-1):
max_heapify(A, array_size, i)
def heap_sort(A):
curr_heap_size = len(A)
build_max_heap(A, curr_heap_size)
while curr_heap_size > 0:
A[0], A[curr_heap_size-1] = A[curr_heap_size-1], A[0]
curr_heap_size -= 1
max_heapify(A, curr_heap_size, 0)
return A