堆

手写堆

堆（是一颗完全二叉树）相关操作（heap堆，size当前元素的个数）

1. 插入一个数 heap[++size] = x; up(size);

2. 求集合当中的最小值 heap[1]

3. 删除最小值 heap[1] = heap[size]; size--; down(1);

4. 删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k);

5. 修改任意一个元素 heap[k] = x; down(k); up(k);

注意对于4，5操作在下标k处的大小可能会改变，如果变大了则会执行down(k)，如果变小了则会执行up(k)，如果不发生改变，均不执行。

小根堆，每个点都小于等于它的孩子节点M

小根堆的down操作和up操作

down操作：根节点（当前节点）和它的孩子节点比较大小，和较小的孩子节点进行交换，知道不需要交换为止

up操作：孩子节点（当前节点）和它的父节点比较大小，如果比起父节点小则进行交换，直到不小于其父节点

注意：基于一维数组堆的下标从1开始比较方便，当下标为x时，左子树left的下标为2x，右子树right的下标为2x+1

(如果是堆的下标从0开始，则左右子树分别为2x+1，2x+2)

堆排序

image-20200714220848546

size = 0

n, m = [int(x) for x in input().split(" ")]
h = [-1] + [int(c) for c in input().split(" ")]
size = n


def down(u: int):
    t = u
    if 2 * u <= size and h[2 * u] < h[t]:
        t = 2 * u
    if 2 * u + 1 <= size and h[2 * u + 1] < h[t]:
        t = 2 * u + 1
    if t != u:
        h[t], h[u] = h[u], h[t]
        down(t)


def up(u: int):
    while u >> 1 and h[u >> 1] > h[u]:
        h[u], h[u >> 1] = h[u >> 1], h[u]
        u >>= 1


for i in range(size >> 1, 0, -1):
    down(i)

for _ in range(m):
    print(h[1])
    h[1] = h[size]
    size -= 1
    down(1)

模拟堆

image-20200714224149765

image-20200714223944760

参考