Data structure cheat sheet

A quick cheat sheet on common algorithms and data structures:

Sorting and Ordering

Simple Sort

Insertion sort.

Quick Sort

The core of the quicksort is dividing the sorting array into half and repeat this operation. The dividing procedure is called partition, and there are two typical implementations of it: Lomuto and Hoare partition. The Lomuto partition process the elements one by one, and swap the elements smaller than the pivot to the left side. Hoare partition goes through the arrays on both ends, swap pairs on the wrong side, and end the progress when the two scan meets.

Quicksort on average takes $\mathrm{\Theta }(nlgn)$ time. Worse case it can cause $\mathrm{\Theta }(n^2)$. There are a number of algorithms based on the idea of doing partitions and processing either or both sides of it. If only one side of it is processed, it uses O(n) time.

Median and order statistics

Selecting min/max from the array takes linear time, and selecting the general $k^{th}$ element takes a expected $\mathrm{\Theta }(n)$ time using a method similar to quicksort.

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

Graphs

Storage

Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix.

Mathematical Problems

Permutations and Combinations

Generate next lexicographic permutation

• find the longest non-increasing suffix:

671[5432]

• find the last element that is larger than the previous one:

6[7]1[5]432

• swap

6[5]1[7]432

• reverse the tail:

6[5]1[2347]