Heap

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

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

  • index of lChild = my index * 2 + 1

  • index of rChild = my index * 2 + 2

  • index of parent = (my index - 1) / 2

insert O(log n) update O(log n) get/top O(1) pop O(log n) heapify O(n)

为什么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)

PreviousInitial pageNextGraph

Last updated