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

# Heap

堆，也被称为Priority Queue，用于维护变化的数据集的最优值

堆是一个完全二叉树 (complete binary tree)，且任意节点小于/大于它的所有descendant。根节点最小的被称为MIN HEAP，根节点最大的被称为MAX HEAP

![](https://3169941669-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M1EdxtEZWsdM5mrgEPz%2F-M1Edzf359xMIGlVhvSE%2F-M1EfjceH7-SyIgIfOsB%2Fheap.JPG?alt=media\&token=610394d2-0e9a-4c22-ada7-38b0e8a717dd)

* index of lChild = my index \* 2 + 1
* index of rChild = my index \* 2 + 2
* index of parent = (my index - 1) / 2

{% hint style="info" %}
**insert**  O(log n)    **upda**t**e** O(log n)    **get/top** O(1)    **pop** O(log n)     **heapify** O(n)
{% endhint %}

为什么insert是从O(log n), 可以想象上图，一个已经排好序的min heap，插入新元素的时候，把他放在2这个节点的右子节点，然后进行更新，如果比根节点还小，换位置，否则就留在这里

## Top K Smallest Element from unsorted array of size N

**Solution 1**  

Heapify all elements O(n)  and call pop() k times to get the k smallest k candidates 

Total time O(n + k log n)

**Solution 2**

首先构造一个size 为k的max heap，对他进行Heapify O(k)，然后遍历剩下的(n - k)个元素。对于每一个新的元素，如果他大于max heap最顶部的元素，则ignore他，否则，将这个元素插入到heap中

Total time  O(k + (n-k) log k)