> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/heap.md).

# Heap

完全二叉树，因此用数组存储更为便捷。root存min或者max.

每个父结点都比子节点小(大)。插入一个元素是先把那个元素放在末尾，然后不断和parent swap, sift up。

删除一个元素即把root删了，然后把末尾元素放到root, 再不断sift down. sift down过程是不断和子节点比较，把最小(大)swap到parent。

O(1)时间获得min, O(lgn)时间插入或者删除一个元素。O(n)时间建立一个堆，必须从底向上建立，否则需要O(nlgn)。

堆常用于排序。

存储方式是用数组，叶节点分别在父节点位置k的2k + 1和2k+2处。node k 的parent在(k-1)/2处。

用于在k个元素中找最小/最大。

维持一个size为k的heap, 每次弹出一个最小的它指向的可能是下一个最小的，把它指向的放入heap中。