第十五讲：堆

# -*- coding:utf-8 -*-
# 堆
class Heap(object):
    def __init__(self):
        self.dataList = [None]      # 第一个元素设为 None 避免 0 下标
    def size(self):
        return len(self.dataList) - 1
    def leftChild(self, root):
        return root * 2
    def rightChild(self, root):
        return root * 2 + 1
    def father(self, node):
        return node / 2
    def heapify(self, root):
        if root > self.size():
            return
        leftNode = self.leftChild(root)
        rightNode = self.rightChild(root)
        largest = root
        if leftNode <= self.size():     # 防止这个点是叶子结点
            if self.dataList[leftNode] > self.dataList[largest]:
                largest = leftNode
        if rightNode <= self.size():     # 防止这个点是叶子结点
            if self.dataList[rightNode] > self.dataList[largest]:
                largest = rightNode
        if largest != root:
            self.dataList[root], self.dataList[largest] = self.dataList[largest], self.dataList[root]
            self.heapify(largest)
    def buildHeap(self):
        for i in range(self.size() / 2, 0, -1):  # 从最后一个非叶子结点遍历
            self.heapify(i)
    def getMax(self):
        if self.size() == 0:  # 判断堆是否为空
            return None
        ret = self.dataList[1]  # 保存堆顶元素
        self.dataList[1] = self.dataList[-1]  # 把最后一位移到第一位
        del self.dataList[-1]  # 删除最后一位
        self.heapify(1)  # 重新建堆
        return ret
    def insert(self, data):
        self.dataList.append(data)  # 存到最后面
        nowIndex = self.size()  # 拿到下标（就是长度）
        pre = self.father(nowIndex)  # 拿到父亲节点下标
        while self.dataList[pre] < data and nowIndex != 1:  # 遍历父节点 直到为根结点或者父节点比data大
            self.dataList[pre], self.dataList[nowIndex] = self.dataList[nowIndex], self.dataList[pre]
            nowIndex = pre
            pre = nowIndex / 2
heap = Heap()
heap.insert(9)
heap.insert(10)
heap.insert(7)
heap.insert(12)
heap.insert(3)
heap.insert(4)
# print heap.getMax()
# print heap.getMax()
# print heap.getMax()
# print heap.getMax()
# print heap.getMax()
# print heap.getMax()
# print heap.getMax()
heap.insert(9)
heap.insert(8)
heap.insert(7)
heap.insert(7)
heap.insert(12)
# print heap.getMax()
heap.dataList = [None, 1, 2, 3, 4, 5, 6, 7]
heap.buildHeap()
# print heap.getMax()