Data structure cheat sheet

A quick cheat sheet on common algorithms and data structures:

Tree-based Structures

Heap

A (binary) heap is a complete binary tree that keeps a sepcific condition of its nodes: For a max-heap, $A[parent[i]]>=A[i]$, for a min-heap, $A[parent[i]]<=A[i]$. A heap can be used to maintain a priority queue. A heap is often stored as a continous vector.

Heapify

Heapify is a fundamental operation to keep the heap property when there is a new node inserted into the root.

Complexity: $\mathrm{\Theta }(lgn)$. You can prove that using recusion master theroem.

Build a heap

To build a heap, call heapify() n/2 times for all non-leaf nodes.

Complexity: $\mathrm{\Theta }(n)$

Heapsort

To sort an array in increasing order, build a max heap, put the first element to the final position of the array, and maintain the heap property by calling heapify with the remaining element.

Complexity:$\mathrm{\Theta }(nlgn)$

Priority Queue

A (max) priority queue support four operations: insert, max, extract-max, increase-key. With a heap, these four operations can be done using $\mathrm{\Theta }(lgn)$, $\mathrm{\Theta }(1)$, $\mathrm{\Theta }(lgn)$, $\mathrm{\Theta }(lgn)$ time.

Codes

void max_heapify(Node* A, int size, int start) {
    auto largest = start;
    if(start * 2 < size && A[largest] < A[start * 2])
        largest = start * 2;
    if(start * 2 + 1 < size && A[largest] < A[start * 2 + 1])
        largest = start * 2 + 1;
    if(largest != start) {
        swap(A[start], A[largest]);
        maxheapify(A, size, largest);
    }
}

void build_max_heap(Node* A, int size) {
  for(int i = size / 2; i >= 0; --i) {
    max_heapify(A, size, i);
  }
}