Binary Heap

二叉堆（Binary Heap） 是使用完全二叉树实现的堆，所以其既满足堆的特性，也满足完全二叉树的特性。 对于任何一个节点，其子节点的值全都大于（或小于）父节点。堆顶为最小值的堆称为小顶堆 (Min Heap)，堆顶为最大值则称为大顶堆 (Max Heap)。

因为基于完全二叉树，所以二叉堆的实现一般也是基于数组。

二叉堆各操作的时间复杂度如下：

Operation	Average	Worst case
Insert	$O(1)$	$O(\log n)$
Find-min	$O(1)$	$O(1)$
Delete-min	$O(\log n)$	$O(\log n)$
Decrease-key	$O(\log n)$	$O(\log n)$
Merge	$O(n)$	$O(n)$

又因为经常用来实现比较常用的优先队列，所以很多语言的标准库中的自带了小顶堆（大顶堆通过自定义比较运算的方式实现）的实现，比如Golang, Rust, Python。