def heap_sort(nos):
global size
size = len(nos)
print "the size of the List is : %d " %size
Build_heap(size,nos)
for i in range(size-1,0,-1):
nums[0],nums[i] = nums[i],nums[0]
size = size-1
print "\n", nums
heapify(nos,i,size)
print "heap sort array:" ,nums
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def heapify(nums,i,size):
l = left_child(i)
r = right_child(i)
if l <= size and r <= size:
if r != size:
if nums[l] >= nums[r]:
max = nums[l]
max_index = l
elif nums[l] <= nums[r]:
max = nums[r]
max_index = r
if nums[i] >= max:
print nums
return
elif nums[i] <= max:
nums[i],nums[max_index] = max,nums[i]
heapify(nums,max_index,size)
else:
nums[i],nums[l] = nums[l],nums[i]
print nums
# build a heap A from an unsorted array
def Build_heap(size,elements):
iterate = size//2-1
for i in range(iterate,-1,-1):
print "In %d iteration" %i
heapify(elements,i,size)
print "heapified array is : " ,elements
if __name__ == '__main__':
#get input from user
nums = [6,9,3,2,4,1,7,5,10]
#sort the list
heap_sort(nums)
Output which I get is something like this:
the size of the List is : 9
In 3 iteration
[6, 9, 3, 10, 4, 1, 7, 5, 2]
In 2 iteration
[6, 9, 7, 10, 4, 1, 3, 5, 2]
In 1 iteration
[6, 10, 7, 9, 4, 1, 3, 5, 2]
[6, 10, 7, 9, 4, 1, 3, 5, 2]
In 0 iteration
[10, 6, 7, 9, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
heapified array is : [10, 9, 7, 6, 4, 1, 3, 5, 2]
heap sort array:
[9, 7, 6, 4, 1, 3, 5, 2, 10]
I tried implementing a heap sort algorithm in python. The final output is not sorted. There is something wrong in the heapify operation which I tried to figure out, but I couldn't find it.
Can someone point out what's wrong in my code and propose a solution for it?
The first item(0) was swaped with the last item. To keep max-heap invairant, you should call heapify with 0.
def heap_sort(nos):
size = len(nos)
build_heap(size,nos)
for i in range(size-1,0,-1):
nums[0],nums[i] = nums[i],nums[0]
size -= 1
heapify(nos, 0, size) # <--- i -> 0