堆

【概述】

堆（Heap），是一棵树，其每个结点都有一个值，且每个结点的值都大于等于或小于等于其父结点的值

当每个结点的值都大于等于其父结点的值时，称为大根堆；每个结点的值都小于等于其父结点的值时，称为小根堆

在 C++ 的 STL 中，优先队列 priority_queue 默认就是一个大根堆，在改写其比较算子 greater 后，可将其改为小根堆

一些功能强大的堆还支持可持久化，即对任意历史版本进行查询或操作，从而产生新的版本

【堆的分类】

常用的堆有二叉堆、配对堆、左偏树、二项堆、斐波那契堆等

下面以这些堆的小根堆为例，给出其基本操作的时间复杂度比较

操作	二叉堆	配对堆	左偏树	二项堆	斐波那契堆
插入	$O(\log n)$	$O(1)$	$O(\log n)$	$O(1)$	$O(1)$
查询最小值	$O(1)$	$O(1)$	$O(1)$	$O(\log n)$	$O(1)$
删除最小值	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
合并	$O(n)$	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$
减小一个元素的值	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$
是否可持久化	是	否	是	是	否

习惯上，不加限定提到堆时往往都指二叉堆