I15*_*159 13 python sorting computer-science heapsort
我正在尝试用Python实现Heap Sort,但我似乎无法做到正确.我试图实现这个伪代码,但我的代码没有排序!它只是筛选到荒谬的效果.我倾向于认为问题出在这一行:
将堆的根(最大值)与堆的最后一个元素交换
我如何获得最大值？
这就是我所拥有的:
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)
我发现了一个几乎同样问题的例子:
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
结果不同,但两者都很荒谬:
>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]
>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]
Sky*_*ler 17
我如何获得最大值？你不需要"得到"它.根正好是最大值,这是堆的已定义属性.
如果您觉得难以理解堆排序,本章将非常有用.
我重写了你的代码:
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)
它给:
[-2, 1, 2, 3, 5, 7, 56]
我找到了它并且几乎弄清楚它是如何工作的：
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)
这个实现是根据我自己对算法的理解编写的。它更长，但对我来说，这个算法在这个实现中更加清晰。当您需要理解算法时，长命名很有帮助，因此我保留了所有长名称。
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()
以及优化版本：
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)