I'm trying to implement Heap Sort in Python, but I can't seem to get it right. I've tried to implement this pseudo code, but my code does not sort! It just sifts to ridiculous effect. I'm inclined to think that the problem is in this line:
swap the root(maximum value) of the heap with the last element of the heap
How do I get the maximum value?
That is what I have:
def my_heap_sort(sqc):
def heapify(count):
start = (count-2)/2
while start >= 0:
sift_down(start, count-1)
start -= 1
def swap(i, j):
sqc[i], sqc[j] = sqc[j], sqc[i]
def sift_down(start, end):
root = start
while (root * 2 + 1) <= end:
child = root * 2 + 1
temp = root
if sqc[temp] < sqc[child]:
temp = child+1
if temp != root:
swap(root, temp)
root = temp
else:
return
count = len(sqc)
heapify(count)
end = count-1
while end > 0:
swap(end, 0)
end -= 1
sift_down(0, end)
And I found an example with almost the same problem:
def heap_sort_example(a):
def heapify(a):
start = (len(a) - 2) / 2
start -= 1
def sift_down(a, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and a[child] < a[child+1]:
child += 1
if child <= end and a[root] < a[child]:
a[root], a[child] = a[child], a[root]
root = child
else:
return
heapify(a)
end = len(a) - 1
while end > 0:
a[end], a[0] = a[0], a[end]
sift_down(a, 0, end-1)
end -= 1
The results are different, but both are ridiculous:
>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]
>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]
I found it and almost figured how it works:
def heapsort(sqc):
def down_heap(sqc, k, n):
parent = sqc[k]
while 2*k+1 < n:
child = 2*k+1
if child+1 < n and sqc[child] < sqc[child+1]:
child += 1
if parent >= sqc[child]:
break
sqc[k] = sqc[child]
k = child
sqc[k] = parent
size = len(sqc)
for i in range(size/2-1, -1, -1):
down_heap(sqc, i, size)
for i in range(size-1, 0, -1):
sqc[0], sqc[i] = sqc[i], sqc[0]
down_heap(sqc, 0, i)
This implementation is written based on my own understanding of the algorithm. It is longer, but to me this algorithm is much clearer in this implementation. Long naming is help when you need to understand the algorithm, so I left intact all the long names.
def heapsort(sequence):
sequence_length = len(sequence)
def swap_if_greater(parent_index, child_index):
if sequence[parent_index] < sequence[child_index]:
sequence[parent_index], sequence[child_index] =\
sequence[child_index], sequence[parent_index]
def sift(parent_index, unsorted_length):
index_of_greater = lambda a, b: a if sequence[a] > sequence[b] else b
while parent_index*2+2 < unsorted_length:
left_child_index = parent_index*2+1
right_child_index = parent_index*2+2
greater_child_index = index_of_greater(left_child_index,
right_child_index)
swap_if_greater(parent_index, greater_child_index)
parent_index = greater_child_index
def heapify():
for i in range((sequence_length/2)-1, -1, -1):
sift(i, sequence_length)
def sort():
count = sequence_length
while count > 0:
count -= 1
swap_if_greater(count, 0)
sift(0, count)
heapify()
sort()
And optimized version:
def opt_heapsort(s):
sl = len(s)
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+2 < unsorted:
gtci = i_gt(pi*2+1, pi*2+2)
swap(pi, gtci)
pi = gtci
# heapify
for i in range((sl/2)-1, -1, -1):
sift(i, sl)
# sort
for i in range(sl-1, 0, -1):
swap(i, 0)
sift(0, i)