Heap

https://en.wikipedia.org/wiki/Heap_(data_structure)

• Originally coined in the context of heapsort, also refers to “garbage-collection storage”.
• (binary) Heap is a nearly perfect complete binary-tree.
• Max-heap and min-heap properties. For max-heap, A[parent(i)] >= A[i], i.e. the maximum is stored at the root, the same applies to subtrees.
• More specifically, A[i] >= A[2i + 1] and A[2i + 2]. Alternatively, parent(i) = floor((i - 1) / 2).
• Can be used to implement a priority-queue.
• A special implementation: fibonacci-heap, in which INSERT and DECREASE-KEY takes only $O(1)$ time.

Procedures

• max-heapify: $O(\lg n)$, or $O(h)$, combine two heaps and maintain the max-heap property, by compare and exchange a node with the larger one of its two children
• build-max-heap
  • $O(n)$, the tight bound is derived through summation.
  • Creates a heap from unsorted array.
  • Calling max-heapify from $\lfloor n/2\rfloor$ down to $1$.
• heapsort: $O(n\lg n)$.