我正在尝试用Python实现Heap Sort，但我似乎无法做到正确。我试图实现这个pseudo code，但我的代码没有排序！它只是筛选到荒谬的效果。我倾向于认为问题出在这一行：
将堆的根（最大值）与堆的最后一个元素交换
我如何获得最大值？
这就是我所拥有的：
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]
我如何获得最大值？你不需要“得到”它。根正好是最大值，这是堆的已定义属性。
如果您觉得难以理解堆排序，this chapter将非常有帮助。
我重写了你的代码：
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]
如果你有push和pop，或者正在使用内置的heapq lib，请尝试记录解决方案：
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]
选择排序是一种相对直接的排序算法：遍历一个数组，提取前n个元素的最小值，然后提取下一个n-1个元素的min ......现在这将是O（n ^ 2）算法。
由于你总是提取一分钟，你应该考虑使用最小堆。它在O（log n）时间内提取min。提取最小n次导致O（n * log n）时间。
所以对于堆排序，只需要构建一个堆（heapify O（n））并遍历数组并提取最少n次。
你可以使用python heap来构建堆或构建自己的堆。
def heapsort(l):
hp = make_heap(l)
for i in range(len(l)):
yield hp.extract_min()
我发现heapify的不同实现，堆排序的“心脏”在internetz上并不清楚。以下是我通过添加一个简单但明确的“堆化”示例来帮助社区的谦虚尝试。我使用向量来避免阵列操作的额外混乱。
此方法堆积数组的1个单元格。要堆积整个数组，你需要一个循环，从数组的中间运行它，移动到开始。返回的向量必须与我们在下一次迭代中发送的向量相同，否则它就是一团糟。例如：
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
我找到了它，几乎想到它是如何工作的：
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)
堆排序示例以及如何最初构建堆的示例
def findMin(heapArr,i,firstChildLoc,secondChildLoc):
a = heapArr[i]
b = heapArr[firstChildLoc]
c = heapArr[secondChildLoc]
return i if ((a < b) and (a < c)) else firstChildLoc if (b < c) else secondChildLoc
def prelocateUp(heapArr):
l = len(heapArr)
i = l-1
while True:
parentLoc = (i+1)/2 - 1
if parentLoc >= 0:
if heapArr[parentLoc] > heapArr[i]:
temp = heapArr[parentLoc]
heapArr[parentLoc] = heapArr[i]
heapArr[i] = temp
else :
break
i = parentLoc
return heapArr
def prelocateDown(heapArr):
l = len(heapArr)
i = 0
while True:
firstChildLoc = 2*(i+1) - 1
secondChildLoc = 2*(i+1)
if (firstChildLoc > l-1):
break
elif (secondChildLoc > l-1):
if heapArr[i] > heapArr[firstChildLoc]:
temp = heapArr[i]
heapArr[i] = heapArr[firstChildLoc]
heapArr[firstChildLoc] = temp
break
else :
minLoc = findMin(heapArr,i,firstChildLoc,secondChildLoc)
if minLoc !=i:
temp = heapArr[i]
heapArr[i] = heapArr[minLoc]
heapArr[minLoc] = temp
i = minLoc
else :
break
return heapArr
def heapify(heapArr,op):
if op==1:
heapArr = prelocateUp(heapArr)
else :
heapArr = prelocateDown(heapArr)
return heapArr
def insertHeap(heapArr,num):
heapArr.append(num)
heapArr = heapify(heapArr,1)
return heapArr
def getMin(heapArr):
ele = heapArr[0]
heapArr[0] = heapArr[-1]
heapArr.pop(-1)
heapArr = heapify(heapArr,2)
return ele,heapArr
a=[5,4,8,2,6]
heapArr = []
for i in xrange(0,len(a)):
heapArr = insertHeap(heapArr,a[i])
#No
sortedArr = []
for i in xrange(0,len(a)):
[ele,heapArr] = getMin(heapArr)
sortedArr.append(ele)
print sortedArr