堆python实现

堆

• 堆是一颗完全二叉树
• 任意节点的左孩子和右孩子比该节点值大时，是小顶堆
  任意节点的左孩子和右孩子比该节点值小时，是大顶堆
• 堆数次序是是二叉树的层次遍历
• 堆存储在列表中

堆的操作
①heapify：维护堆状态,也叫堆化。先假设有了一个完整的堆，当根节点变化时，需要重新维护堆状态的动作。
②build_heap：建堆，建堆需要从底层建起，找到最后一个节点的父节点x，heapify(x)得到x,x_l_child,x_r_child满足堆结构，再找x-1节点y，heapify(y)得到y,y_l_child,y_r_child满足堆结构，再找x-2，x-3...逆序遍历后，每次都是底层堆已经完整，只有root节点不满足大小，依次heapify后就完成了建堆操作。时间复杂度O(n)
③get_top：取堆顶，弹出堆顶后，把堆尾移动到堆顶，然后heapify
④insert：插入的数据和父节点比较大小，不满足就交换，然后递归比较。直到满足条件或到走到堆顶

应用场景
topK问题，优先级队列

代码实现

class MyHeap(object):
    def __init__(self):
        # i从0开始数,建立大顶堆
        # i从1数,father=i//2;    lchild=i*2;   rchild=i*2+1
        # i从0数,father=(i-1)//2;lchild=i*2+1; rchild=i*2+1+1
        self.data_list = []
        self.top = 0

    def heap_size(self):
        return len(self.data_list) - 1

    def _swap(self, index_a, index_b):
        self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a]

    def _father(self, i):
        return (i - 1) // 2

    def _lchild(self, i):
        return i * 2 + 1

    def _rchild(self, i):
        return i * 2 + 1 + 1

    # 堆的操作:维护堆状态(堆化),堆的top节点发生变化时,重新维护堆的状态
    def heapify(self, root):
        # 如果堆的root不是最大的,那么就和左右孩子中较大的x进行交换,然后top改成x，递归堆化，直到没有满足条件或者到底为止
        if root > self.heap_size():
            return
        left_node = self._lchild(root)
        right_node = self._rchild(root)
        largest_node = root

        if left_node <= self.heap_size() and self.data_list[left_node] > self.data_list[largest_node]:
            largest_node = left_node
        if right_node <= self.heap_size() and self.data_list[right_node] > self.data_list[largest_node]:
            largest_node = right_node
        if largest_node != root:
            self._swap(largest_node, root)
            self.heapify(root=largest_node)

    # 堆的操作:建堆，找到最后一个node节点的父节点,然后倒着堆化
    # 因为建堆是只能从底下往上建,从上边之间改堆的节点,堆就会塌了
    def build_heap(self, data_list):
        self.data_list = data_list
        last_node = self.heap_size()
        last_node_parent = self._father(last_node)
        for i_node in range(last_node_parent, -1, -1):
            self.heapify(i_node)

    # 堆的操作:取堆顶
    def get_heap_top(self):
        if self.heap_size() == 0:
            return None
        res = self.data_list[self.top]
        # 把堆的最后一个元素和堆顶交换,然后重新堆化
        self.data_list[self.top] = self.data_list.pop()
        self.heapify(self.top)
        return res

    # 堆的操作:插入操作
    def insert(self, data):
        self.data_list.append(data)
        new_data_index = self.heap_size()
        father_index = self._father(new_data_index)
        while self.data_list[father_index] < data and new_data_index != self.top:
            self._swap(father_index, new_data_index)
            new_data_index = father_index
            father_index = self._father(new_data_index)


if __name__ == '__main__':
    data_list = [1, 2, 3, 4, 5, 6, 7]
    s = MyHeap()
    s.build_heap(data_list=data_list)
    print(s.data_list)
    print(s.get_heap_top())
    print(s.get_heap_top())
    print(s.get_heap_top())
    s.insert(data=8)
    print(s.get_heap_top())