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.

void maxheapify(Node* array, 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);
    }
}