实现python的堆类

# 堆
# str写‘min’，‘max’，选择小顶堆还是大顶堆
# down，up是基本操作
# 数组树，完全二叉树
# 2m为左儿子，2m+1为右儿子
class heap: 
    # 初始化
    # 初始化堆空间
    # 堆的元素个数
    # 选择大小顶堆
    # 用lambda表达式大小堆
    # 默认小根堆
    def __init__(self, str = 'min'): # 默认小顶堆
        self.h = [0] * 100010
        self.size = 0
        if str == 'min':
            self.func = lambda x, y :x < y
        elif str == 'max':
            self.func = lambda x, y :x > y 

    # 元素下降
    def down(self, u):
        t = u
        l, r = u * 2, u * 2 + 1
        if l <= self.size and self.func(self.h[l], self.h[t]): t = l
        if r <= self.size and self.func(self.h[r], self.h[t]): t = r
        if u != t:
            self.h[t], self.h[u] = self.h[u], self.h[t]
            self.down(t)

    # 元素上升
    def up(self, u):
        while u//2 > 0 and self.func(self.h[u], self.h[u//2]):
            self.h[u // 2], self.h[u] = self.h[u], self.h[u // 2]
            u = u // 2

    # 建堆，执行n/2次down
    def build(self, arr):
        self.size = len(arr)
        self.h[1 : 1 + self.size] = arr
        i = self.size // 2
        while i > 0:
            self.down(i)
            i -= 1

    # 找到最值
    def top(self):
        return self.h[1]

    # 插入值
    def insert(self, x):
        self.size += 1
        self.h[self.size] = x
        self.up(size)

    # 删除堆顶值
    def pop(self):
        self.h[1] = self.h[self.size]
        self.size -= 1
        self.down(1)

    # 移除任意值
    def remove(self, k):
        self.h[k] = self.h[self.size]
        self.size -= 1
        self.down(k)
        self.up(k)

    # 修改任意值  
    def change(self, k, x):
        self.h[k] = x
        self.down(k)
        self.up(k)