Heap Sort: how to sort?
How do I get the maximum value? You don't need to "get" it. The root is exactly the maximum, that's a defined property of a heap.
If you feel tough to understand heap sort, this chapter will be extremely helpful.
I rewrote your code:
def swap(i, j):
sqc[i], sqc[j] = sqc[j], sqc[i]
def heapify(end,i):
l=2 * i + 1
r=2 * (i + 1)
max=i
if l < end and sqc[i] < sqc[l]:
max = l
if r < end and sqc[max] < sqc[r]:
max = r
if max != i:
swap(i, max)
heapify(end, max)
def heap_sort():
end = len(sqc)
start = end // 2 - 1 # use // instead of /
for i in range(start, -1, -1):
heapify(end, i)
for i in range(end-1, 0, -1):
swap(i, 0)
heapify(i, 0)
sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)
It gives:
[-2, 1, 2, 3, 5, 7, 56]
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)
edit:
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()
edit:
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)
I find that the different implementations of heapify, the "heart" of heap sort are not clear on the internetz. Here is my humble attempt to help the community by adding a simple but clear example of "heapify". I use vectors to avoid the extra confusion of array manipulation.
This method heapifies 1 cell of the array. To heapify the whole array you need a loop, run it from middle of array, moving to beginning. The returned vector MUST be the same one we send in the next iteration, otherwise it's a mess. eg:
for (int i = myvector.size()/2; i >= 0; i--) { in = Heapify(in, i);}
vector_of_int Sort::Heapify(vector_of_int in_vector, int in_index)
{
int min_index = in_index; // Track index of smallest out of parent and two children.
int left_child_index = 0;
int right_child_index = 0;
int vector_size = in_vector.size();
left_child_index = LeftChildIndex(in_index);// index of left child, at position 2*in_index
right_child_index = left_child_index + 1;// index of right child, at position 2*in_index + 1
// If left_child_index is not overflowing, suggest swap...
if ((left_child_index) < vector_size)
{
// If parent larger than left child, min_index remembers left child position
if (in_vector[min_index] > in_vector[left_child_index])
{ min_index = left_child_index; }
}
// If right_child_index is is not overflowing, suggest swap...
if (right_child_index < vector_size)
{
// If parent larger than right child, min_index remembers right child position
if (in_vector[min_index] > in_vector[right_child_index])
{ min_index = right_child_index; }
}
// Now min_index has the index of the smallest out of parent and it's two children.
// If the smallest is not the parent, swap parent and smallest.
if (min_index != in_index)
{
in_vector = swap(in_vector, in_index ,min_index);
in_vector = Heapify(in_vector, min_index); // RECURSION IS HERE
}
return in_vector;
}
// End heapify
If you have push and pop, or are using built-in heapq lib, try documented solution:
from heapq import heappush, heappop
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]