什么是最大堆
最大堆就是一棵二叉树。满足两点性质：
- 父结点的键值大于子结点的键值。
- 左子树和右子树也是堆。
同理可知什么是最小堆。
一般用数组来表示堆。通过下标可以计算出父节点（i/2)，子节点2×i, 2×i+1。
如何建立最大堆
从堆的一半处开始（剩下的一半是叶子）将子堆的堆顶元素下沉。循环操作直到根。
如何堆排序
建立最大堆之后，堆顶元素为最大。将他与最后的元素交换。最后的元素成为第一个元素后，在[1, count-1]范围内将他下沉，推出下一个堆顶。
重复此操作，count不断减1，直到等于2。
详细带图的流程参见这篇文章
代码：
#max heap
def BuildMaxHeap(numbers, heapCount, less):
# form (heapCount/2) to 1, let heap down
for startIndex in range((int)(heapCount / 2), 0 , -1):
MaxHeapDown(numbers, startIndex, heapCount,less)
pass
def MaxHeapDown(numbers, startIndex, heapCount,less):
child = startIndex*2 # left child
temp = numbers[startIndex-1]
while startIndex <= heapCount / 2:
# find the max child [if child == heapCount, means right child donot exist]
if child < heapCount and less(numbers[child-1], numbers[child]):
child = child + 1
# if parent not less than child, no need to go down.
if not(less(temp, numbers[child - 1])):
break
# if child bigger than parent, lift child up
numbers[startIndex-1] = numbers[child-1]
# parent go down
startIndex = child
child = startIndex*2
numbers[startIndex-1] = temp
def ThenHeapSort(numbers, heapCount, less):
for count in range((int)(heapCount), 1 , -1):
RemoveHeap(numbers, 1, count-1, less)
def RemoveHeap(numbers, startIndex, heapCount, less):
# put the biggest number(first) at the last, like removed. put the last number at first.
numbers[startIndex-1], numbers[heapCount] = numbers[heapCount], numbers[startIndex-1]
# let the first number go down, select the next bigget number
MaxHeapDown(numbers, startIndex, heapCount, less)
def leftless(a,b):
return a<b
def rightless(a,b):
return a>b
def HeapSort(numbers, heapCount, less=leftless):
BuildMaxHeap(numbers, len(numbers), less)
ThenHeapSort(numbers, len(numbers), less)
def TestHeap():
numbers = [16,32,55,61,78,34,78,11,25,64,91,88,67,120]
print(numbers)
HeapSort(numbers, len(numbers))
print(numbers)
HeapSort(numbers, len(numbers), rightless)
print(numbers)
if __name__ == '__main__':
TestHeap()
