堆基础知识

堆是一种树形结构，树的根是堆顶，堆顶始终保持为所有元素的最优值。有最大堆和最小堆，最大堆的根节点是最大值，最小堆的根节点是最小值。堆一般用二叉树实现，成为二叉堆。
二叉堆的典型应用有堆排序和优先队列。

以下以小根堆举例。

¶1.二叉堆的概念

二叉堆是一棵完全二叉树。除了最后一层可能不满，其他都是满的。
二叉堆中的每个节点，都是以它为父节点的子树的最小值。
用数组$A[]$存储完全二叉树，节点数量为$n$，$A[1]$为根节点，有以下性质：
(1)$i>1$的节点，其父节点位与$i/2$;
(2)如果$2i>n$,那么节点$i$没有左孩子；如果$2i+1>n$,那么节点i没有右孩子；
(3)如果节点$i$有孩子，那么它的左孩子是$2i$，右孩子是$2i+1$。
堆的操作：
(1)进堆：每次把元素放进堆，都调整堆的形状，使根节点保持最小。
(2)出堆：每次取出的堆顶，是整个堆的最小值；同时调整堆，是新的堆顶最小。
二叉树只有$O(log_2n)$层，进堆和出堆逐层调整，计算复杂度都为$O(log_2n)$。

¶2.二叉堆的操作

1.上浮
某个节点的优先级上升，或者在堆底加入一个新元素，若父节点比它大，则一直与父结点交换位置，直至父节点比他小或者最终到达根节点停止。
2.下沉
某个节点的优先级下降，或者将根节点替换为一个较大的新元素，每次将其左右子结点中的最小值与其交换，直至比其子节点都小或者到达堆底停止。

¶3.二叉堆的手写代码

【模板】堆

¶小技巧：如果只push元素，只需要up($O(log_2n$))或从n//2~1down($O(n)$)；如果修改某个下标的值（或在不删除的情况下修改第k个插入的数），需要up和down；如果在有删除的情况下修改第k个插入的数，需要将swap换成heap_swap。

¶plus模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import sys
input=lambda:sys.stdin.readline()
write=lambda x:sys.stdout.write(str(x)+'\n')
N=1000005
h=[0]*N
size=0
def down(u):
    global size
    t=u
    if t*2<=size:
        t*=2
        if t+1<=size and h[t+1]<h[t]:
            t+=1
        if h[t]<h[u]:
            h[t],h[u]=h[u],h[t]
            down(t)
    return


n=int(input())
for i in range(n):
    s=input().split()
    if s[0]=='1':
        x=int(s[1])
        size+=1
        h[size]=x
        for i in range(n//2,0,-1):
            down(i)
    elif s[0]=='2':
        write(h[1])
    else:
        h[1]=h[size]
        size-=1
        down(1)

¶《算法竞赛》模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def push(x):
    global size
    size+=1
    h.append(x)
    i=size
    while i>1 and h[i]<h[i//2]:#上浮过程
        h[i],h[i//2]=h[i//2],h[i]
        i//=2

def pop():
    global size
    h[1]=h[size]
    h.pop()
    size-=1
    i=1
    while 2*i<=size:
    #下沉过程
        son=2*i
        if son<size and h[son+1]<h[son]:
            son+=1
        if h[son]<h[i]:
            h[son],h[i]=h[i],h[son]
            i=son
        else:
            break

n=int(input().strip())
h=[0]
size=0
for i in range(n):
    s=input().split()
    if s[0]=='1':
        x=int(s[1])
        push(x)
    elif s[0]=='2':
        print(h[1])
    else:
        pop()

¶4.堆和priority-queue

¶优先队列STL

1
2
3
4
5
6
7
8

import queue
q=queue.PriorityQueue()#默认小根堆
q.put(2)
q.put(1)
q.put(3)
while not q.empty():
    print(q.get())
print(q.qsize())

¶堆STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from heapq import heapify,heappush,heappop,heappushpop,nlargest,nsmallest,heapreplace,merge
h=[]
heapify(h)#将列表创建为最小堆
heappush(h,5)#向堆中加入一个元素
heappush(h,3)
heappush(h,1)
heappush(h,2)
heappush(h,4)
while h:
    print(heappop(h))#弹出并返回堆顶
heappush(h,5)
heappush(h,2)
heappush(h,4)

print(heappushpop(h,3))#存入x,再弹出并返回堆顶
print(heapreplace(h,21))#先弹出并返回堆顶，再存入x

print(h)#输出不是按大小顺序,而是按层遍历(BFS)输出
#以下函数均可设置key排序参数
print(nlargest(3,h))#返回前n个最大的元素
print(nsmallest(3,h))#返回前n个最小的元素
print(list(merge(h,[1,2,3,6])))#将多个可迭代对象合并，原对象有序，则合并结果有序，反之无序
print(list(merge(h,[1,2,5,3])))