Stacks & Queues

Stacks

LIFO (Last-In, First-Out) linear data structures. Operations include push (add element to top), pop (remove top element), and peek (view top element). They are used for function call stacks, expression evaluation, and parenthesis matching.

Queues

FIFO (First-In, First-Out) linear data structures. Operations include enqueue (add to rear), dequeue (remove from front), and peek (view front element). They are used for breadth-first search (BFS) graph traversals and task scheduling.

Binary Trees & BSTs

Binary Trees

Hierarchical data structures or Tree where each node has at most two children, a left and a right node. Traversals include Inorder (left, root, right), Preorder (root, left, right), Postorder (left, right, root), and Level order (breadth-first, uses a queue).

Binary Search Trees (BSTs)

Specialized binary trees, each node value being less than left, and greater than right. This property enables efficient insertion, deletion, and search, O(log N) average-case. Performance comes from maintaining balance e.g. AVL or Red-Black trees.

Binary Tree Node in C

  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };
    

Heaps & Priority Queues

Heaps are complete binary trees satisfying the heap property. Complete means each level is full until the last one filled left-wise. In a Min/Max-heap, each parent node's value is respectively less/greater than or equal to its children's. Commonly implemented using arrays along operations:

• insert, adding element and maintaining heap property
• extract max/min, removing root and re-heapifying
• heapify, building a heap from an array

Heaps efficiently implement Priority Queues, where elements are retrieved based on priority. Applications include finding the top K elements in a collection, event simulation, and in algorithms like Dijkstra's shortest path.

Min-Heap via Python's heapq

In Python, a Heap of the min-heap variant is directly available via the stdlib package heapq. It exposes a set of functions to apply onto a regular list.

  from heapq import *
  heapify(h :=
    [12, 48, 6, 3, 1])    # h = [1, 3, 6, 12, 48]
  heappush(h, 10)         # h = [1, 3, 6, 12, 48, 10]
  heappush(h, 5)          # h = [1, 3, 5, 12, 48, 10, 6]
  heappop(h)              # h = [3, 6, 5, 12, 48, 10]
  heappop(h)              # h = [5, 6, 10, 12, 48]
  heappop(h)              # h = [6, 12, 10, 48]
  heappop(h)              # h = [10, 12, 48]