堆
堆是一个数组，可以看作一个近似的完全二叉树，树中的每一个节点对应于数组中的一个元素。除了最底层的叶节点，往上的所有层都是完全填充的，并且都是从左向右进行填充。表示堆的数组A有两个属性：A.length表示数组大小，A.heap-size表示堆大小，即堆中有多少个元素存在数组中。
算法导论中将根节点的序号设定为1，但实际使用的数组都是从0开始的，即从偶数开始填充堆，那么为了使数组依次逐层进行填充，对于一个节点在数组中的序号i，其左右孩子为:
Left(i): 2i+1
Right(i): 2i+2
根据左右孩子可以将一个序号为i的节点的父节点计算为：
Parent(i): floor((i-1)/2)
最大堆与最小堆
最大堆是父节点的值大于等于子节点的值，反之，最小堆是子节点的值大于等于父节点的值。在堆排序中使用最大堆，最小堆通常用于构造优先队列。
最大堆与堆排序
class Heap:
def __init__(self, array, heap_size = None):
if heap_size is not None:
self.heap_size = heap_size
else:
self.heap_size = len(array)
self.array = array
@classmethod
def left(cls, i):
return (i << 1) + 1
@classmethod
def right(cls, i):
return (i << 1) + 2
@classmethod
def parent(cls, i):
return (i - 1) / 2
@classmethod
def swap(cls, A, i, j):
temp = A[i]
A[i] = A[j]
A[j] = temp
class MaxHeap(Heap):
def __init__(self, array, heap_size = None):
Heap.__init__(self, array, heap_size)
self.build()
def build(self):
for i in xrange(len(self.array)/2, -1, -1):
self.max_heapify(i)
def max_heapify(self, i):
"""
heap: a max heap
i: a heap node index
"""
print i
A = self.array
heap_size = self.heap_size
l = Heap.left(i)
r = Heap.right(i)
largest = i
if l < heap_size and A[largest] < A[l]:
largest = l
if r < heap_size and A[largest] < A[r]:
largest = r
if largest != i:
Heap.swap(A, i, largest)
print i, self.array
self.max_heapify(largest)
def heap_sort(self):
A = self.array
for i in xrange(len(self.array) -1, -1, -1):
Heap.swap(A, i, 0)
self.heap_size -= 1
self.max_heapify(0)
if __name__ == '__main__':
array = [1, 14, 10, 8, 7, 4, 3, 2, 9, 16]
max_heap = MaxHeap(array)
max_heap.heap_sort()
print max_heap.array