python 数据结构之堆及其实现

关于堆的介绍

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

举个例子——大顶堆：

堆的操作

维护堆状态

建堆

取堆顶

新增数据

Python3 代码实现

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 now_index != 1 and self.data_list[pre] < data:
            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())

输出

12
10
9
7
4
3
None
12
7