"""堆是一种完全二叉树，有最大堆和最小堆两种。最大堆：对于每个非叶子结点V，V的值都比它的两个孩子结点大，称为最大堆特性(heap order property),       最大堆里面的根总是储存最大值，最小值储存在叶子结点。最小堆：和最大堆相反，每个非叶子结点V，它的两个孩子的值都比V的值大。"""# 实现最大堆# 首先实现一个数组class Array(object):    def __init__(self, size=32):        self._size = size        self._items = [None] * size    def __getitem__(self, index):        return self._items[index]    def __setitem__(self, index, value):        self._items[index] = value    def __len__(self):        return self._size    def clear(self, value = None):        for i in range(self._size):            self._items[i] = value    def __iter__(self):        for item in self._items:            yield item# 用数组来实现堆。# 因为堆是完全二叉树，舍某结点的下标为i，#  它的父结点为 int((i-1)/2),左孩子结点为2*i + 1， 右孩子结点为2*i +2， 超出下标表示没有孩子结点class MaxHeap(object):    """dmaxsizetring for MaxHeap"""    def __init__(self, maxsize = None):        self.maxsize = maxsize        self._elements = Array(maxsize)        self._count = 0    def __len__(self):        return self._count    def add(self, value):        if self._count>=self.maxsize:            raise Exception("Full")        self._elements[self._count] = value        self._count += 1        self._siftup(self._count-1)    # 因为第一个结点是从0开始的，最后一个结点是结点个数减一        '''        partent = int((n-1)/2)        self._elements[n] = value        while self._elements[n] > self._elements[partent]:            self._elements[n], self._elements[partent] = self._elements[partent], self._elements[n]        '''    def _siftup(self, ndx):     # 递归交换，知道满足最大堆特性        if ndx > 0:            parent = int((ndx-1)/2)            if self._elements[ndx] > self._elements[parent]:                self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]                self._siftup(parent)    def extract(self):      # 拿掉堆的最大值        if self._count <= 0:            raise Exception('empty')        value = self._elements[0]        self._elements[0] = self._elements[self._count-1]   # 把最后一个结点赋值给根结点 然后进行siftdown 操作        self._count -= 1        self._siftdown(0)        return value    def _siftdown(self, ndx):        left = ndx * 2 + 1        right = ndx * 2 +2        largest = ndx        # 保证下标不越界， 左孩子大于该结点， 而且左孩子大于右孩子        if  (left < self._count and            self._elements[left] >= self._elements[largest] and            self._elements[left] >= self._elements[right]):            largest = left   # 把最大的下标赋值给left 孩子        elif (right < self._count and            self._elements[right] >= self._elements[largest] and            self._elements[right] >= self._elements[left]):            largest = right        if largest != ndx:            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]            self._siftdown(largest)# 堆堆倒叙排序def heapsort_reverse(array):    length = len(array)    maxheap = MaxHeap(length)    l = []    for i in range(length):        maxheap.add(i)    for i in range(length):        l.append(maxheap.extract())    return ldef test_max_heap():    import random    n = 5    h = MaxHeap(n)    for i in range(n):        h.add(i)    for i in reversed(range(n)):        assert i == h.extract()    l = list(range(10))    random.shuffle(l)    assert heapsort_reverse(l) == sorted(l, reverse=True)