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: $O(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: $O(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:$O(nlgn)$

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);
  }
}