堆模板

# 初始化堆
def heap_make(nums):
    if len(nums) <= 1:
        return
    size = len(nums)
    # 从最后一个非叶子节点开始做下滤操作
    pa = (size - 2) // 2
    while pa >= 0:
        # 对根节点为pa的子树做下滤操作
        down(pa, nums)
        pa -= 1

# 对根节点为child_tree的子树做下滤操作，让其成为一个堆
def down(child_tree, nums):
    if not nums:
        return
    value = nums[child_tree]
    size = len(nums)
    idx = child_tree
    while idx < size:
        # 先找到左孩子
        swap_idx = idx * 2 + 1
        # 没有左孩子，跳出循环
        if swap_idx >= size:
            break
        # 如果有右孩子，且右孩子大于左孩子，就交换
        if swap_idx < size - 1 and nums[swap_idx] < nums[swap_idx + 1]:
            swap_idx += 1
        # 如果父节点小于最大的子节点，就交换
        if nums[swap_idx] > value:
            nums[idx] = nums[swap_idx]
            idx = swap_idx
        else:
            # 所有子节点都小于该父节点，跳出循环
            break
    nums[idx] = value

# 弹出并获取堆顶元素
def heap_pop(nums):
    # 交换第一个和最后一个元素
    nums[0], nums[-1] = nums[-1], nums[0]
    rtn = nums.pop()
    # 对第一个元素做下滤操作
    down(0, nums)
    return rtn

# 获取堆顶元素
def heap_max(nums):
    return nums[0]

# 将num插入到堆中
def heap_push(nums, num):
    nums.append(num)
    idx = len(nums) - 1
    # 找到父节点
    pa = (idx - 1) // 2
    value = nums[idx]
    # 如果父节点小于该节点，就交换
    while idx > 0 and nums[pa] < value:
        nums[idx] = nums[pa]
        idx = pa
        pa = (idx - 1) // 2
    # 最后将该节点放到合适的位置
    nums[idx] = value

if __name__ == '__main__':
    nums = [1, 4, 3, 7, 0, 6, 9]
    heap_make(nums)
    heap_push(nums, 10)
    heap_push(nums, 12)
    heap_push(nums, 8)
    while nums:
        print(heap_pop(nums))