Data Structures

Heap

Leetcode: 347. Top K Frequent Elements

Intro

A Heap is a binary tree with either of following conditions:

1. MinHeap: Smallest element is at the root. Parent nodes are smaller than or equal to their children.

2. MaxHeap: Largest element is at the root. Parent nodes are larger than or equal to their children.

Heaps are nearly complete binary trees. Meaning that all levels are fully filled except for the last, which is filled from left to right.

Heaps are implemented using arrays, either 1-indexed or 0-indexed, and use simple arithmetic to track parents and children.

1-indexed heaps (more common in textbooks):

• Parent of i: floor(i/2)
• Left child of i: 2i
• Right child of i: 2i + 1

Indices:      _,  1,   2,   3,   4,   5,   6,   7
1-indexed: [ _,  10,  20,  15,  30,  40,  50,  60 ]

                  10 (1)
               /        \
           20 (2)       15 (3)
         /     \       /     \
     30 (4)   40 (5) 50 (6)  60 (7)

0-indexed heaps:

• Parent of i: floor(i-1/2)
• Left child of i: 2i + 1
• Right child of i: 2i + 2

Indices:      0,  1,   2,   3,   4,   5,   6
0-indexed: [ 10, 20,  15,  30,  40,  50,  60 ]

                  10 (0)
               /        \
           20 (1)       15 (2)
         /     \       /     \
     30 (3)   40 (4) 50 (5)  60 (6)

Heap operations are, push(), pop(), and peek(). In other words, insert(), remove(), and peek()

Push(): O(log n) Adds a new elements to the bottom right end of the heap, and performs bubbleUp() to restore the heap property. This takes O(log n) which correlates with the height of the tree

Pop(): O(log n) Removes the root, and place the bottom right end element at the root, and performs bubbleDown() to restore the heap property.

Peek(): O(1) Returns the root element without modifying the heap.

Monotone Stack (to-do)

Leetcode: stack 84. Largest Rectangle in Histogram Leetcode: two pointers 42. Trapping Rain Water

Segment Tree (to-do)

Leetcode: 84. Largest Rectangle in Histogram

Union Find

Leetcode: 128. Longest Consecutive Sequence

Intro

Union Find is a general-purpose data structure used in problems involving connectivity, grouping or clustering.

Operations

1. Union(x, y): Connects two elements by making them part of the same group, by giving them the same parent

2. Find(elem): Finds the representative (or root) of the group containing the element

Path Compression Optimization

Here is our initial structure before path compression

1 → 2 → 3 → 4 → 5

After performing find(1) with path compression, the structure becomes:

1 → 5  
2 → 5  
3 → 5  
4 → 5  
5 → 5