heap.py

#!/usr/bin/env python
# -*- coding: utf-8

# 堆是一个二叉树
# 叶子节点只存在最下面两层
# 从根节点到倒数第二层，是一个完全二叉树
# 一个节点不可能只有右孩子
# 一个节点的左孩子和右孩子都比这个节点大（或者小）

class Heap(object):
    def __init__(self):
        self.data_list = [None]
    def size(self):
        return len(self.data_list) - 1
    def left_child(self, root):
        return root * 2
    def right_child(self, root):
        return root * 2 + 1
    def father(self, node):
        return node / 2
    def heapify(self, root):
        if root > self.size():
            return
        left_node = self.left_child(root)
        right_node = self.right_child(root)
        largest = root
        if left_node <= self.size():
            if self.data_list[left_node] > self.data_list[largest]:
                largest = left_node
        if right_node <= self.size():
            if self.data_list[right_node] > self.data_list[largest]:
                largest = right_node
        if largest != root:
            self.data_list[root], self.data_list[largest] = self.data_list[largest], self.data_list[root]
            self.heapify(largest)
    def build_heap(self):
        for i in range(self.size()/2, 0, -1):
            self.heapify(i)
    def get_max(self):
        if self.size() == 0:
            return None
        ret = self.data_list[1]
        self.data_list[1] = self.data_list[-1]
        del self.data_list[-1]
        self.heapify(1)
        return ret
    def insert(self, data):
        self.data_list.append(data)
        now_index = self.size()
        pre = self.father(now_index)
        while self.data_list[pre] < data and now_index != 1:
            self.data_list[pre], self.data_list[now_index] = self.data_list[now_index], self.data_list[pre]
            now_index = pre
            pre = now_index / 2
heap = Heap()
heap.insert(9)
heap.insert(10)
heap.insert(7)
heap.insert(12)
heap.insert(3)
heap.insert(4)
print (heap.get_max())
print (heap.get_max())
print (heap.get_max())
print (heap.get_max())
print (heap.get_max())
print (heap.get_max())
print (heap.get_max())
heap.insert(10)
heap.insert(9)
heap.insert(8)
heap.insert(7)
heap.insert(7)
heap.insert(12)
print (heap.get_max())
heap.data_list = [None, 1, 2, 3, 4, 5, 6, 7]
heap.build_heap()
print (heap.get_max())