Basics

Heap: 披着二叉树羊皮的数组

基本操作

• add: o(logn), sift up, 相当于一次 heapify
• remove / delete
  • 最后: o(logn), sift down, 相当于一次 heapify
  • 任意: o(n), 用hashmap o(logn)

• 1次 heapify: o(logn)

• build heap <=> n 次 heapify

  • sift down, o(n)
  • sift up, o(nlogn)

• extract max

  • o(1) + o(logn) heapify

• heap sort

  • 一般都用 max heap
  • 交换 max 与 last (length - 1) 位置
  • sift down. 与 build heap sift down 不同的是：每一次sort都要top sift down, 而 build tree 不是都从 top sift down
  • o(nlogn)

PriorityQueue

• multithreading 下使用: PriorityBlockingQueue
• Array.sort(pq.toArray())

Tips:

• 在 index 从 0 开始的数组中
  • father i 的 left child: 2 * i + 1
  • father i 的 right child: 2 * i +2
  • child 的 father: floor((i - 1) / 2)

kth largest - min heap

• k size heap
• pq.peek()
• partition is quicker

(top) k largest - min heap e.g. 国家队k member vs upcoming 选拔队 淘汰赛 淘汰最小的

• k size heap
• compare heap peek() - min with upcoming value

Problems

heapify: http://www.lintcode.com/en/problem/heapify/

ugly number ii: http://www.lintcode.com/en/problem/ugly-number-ii/

merge k sorted list: http://www.lintcode.com/problem/merge-k-sorted-lists/

merge k sorted arrays: http://www.lintcode.com/problem/merge-k-sorted-arrays/

data stream median: http://www.lintcode.com/problem/data-stream-median/

top k largest numbers: http://www.lintcode.com/problem/top-k-largest-numbers/

top k largest numbers ii: http://www.lintcode.com/en/problem/top-k-largest-numbers-ii/

kth smallest number in sorted matrix http://www.lintcode.com/problem/kth-smallest-number-in-sorted-matrix/