Advanced Data Structures & Applications: Heaps, Tries, Disjoint Sets, and Graph Algorithms

TAKEAWAYS:

• Heaps (min-heap/max-heap) enable efficient priority queues with $O(\log n)$ insert/delete, used in scheduling and Dijkstra’s algorithm.
• Tries (prefix trees) optimize string searches (autocomplete, dictionaries) with $O(L)$ lookup time per word of length $L$.
• Disjoint-set forests (Union-Find) manage dynamic connectivity problems (e.g., network redundancy, social network friend groups) with near-constant-time operations.
• Graph algorithms (Kruskal’s, Prim’s, Dijkstra’s) solve minimum spanning trees and shortest paths, critical for routing (NTC networks, Pathao deliveries) and dependency resolution (software builds).
• Topological sorting linearizes directed acyclic graphs (DAGs), used in task scheduling (e.g., course prerequisites, dependency resolution in software).
• Trade-offs between time/space complexity and real-world constraints (e.g., memory vs. speed in heaps vs. balanced BSTs) dictate choice of data structure.

1. Priority Queues and Heaps

1.1 Definition and Properties

A heap is a complete binary tree where each node satisfies the heap property:

• Min-heap: Parent ≤ children (smallest element at root).
• Max-heap: Parent ≥ children (largest element at root).

Key operations:

• insert(key): $O(\log n)$
• extract-min/max(): $O(\log n)$
• get-min/max(): $O(1)$

1.2 Array Representation

Heaps are stored in arrays for efficiency:

• For a node at index i:
  • Left child: 2i + 1
  • Right child: 2i + 2
  • Parent: $\lfloor (i-1)/2\rfloor$

graph TD
    A["Root (i=0)"] --> B["Left (i=1)"]
    A --> C["Right (i=2)"]
    B --> D["Left (i=3)"]
    B --> E["Right (i=4)"]
    C --> F["Left (i=5)"]
    C --> G["Right (i=6)"]

Example: Min-heap for [3, 9, 2, 1, 4] (array indices 0–4):

[1, 3, 2, 9, 4]

Visualization:

**1.3 Operations: Insert and Extract-Min

Insertion:

1. Add the new element at the end of the array.
2. Bubble-up (heapify-up) to restore the heap property.

Extract-Min:

1. Remove the root (min element).
2. Replace it with the last element in the array.
3. Bubble-down (heapify-down) to restore the heap property.

Trace: Insert 5 into [1, 3, 2, 9, 4] (min-heap)

Trace: Extract-Min from [1, 3, 2, 5, 4]

1.4 Applications

• Dijkstra’s algorithm: Priority queue for selecting the next node to explore.
• Job scheduling: Highest-priority tasks executed first (e.g., Pathao’s ride allocation).
• Merge K sorted lists: Heap merges lists in $O(N\log K)$ time.

In the real world:

• Pathao’s ride allocation: Uses a max-heap to prioritize drivers with the highest availability score (distance, response time) for nearby passengers.
• NTC’s network routing: Dijkstra’s algorithm (with a min-heap) finds the shortest path for data packets between routers.
• WhatsApp’s message delivery: Priority queues ensure urgent messages (e.g., calls, alerts) are processed before regular chats.

2. Tries (Prefix Trees)

2.1 Definition

A Trie (pronounced "try") is a tree-like data structure for storing strings, where:

• Each node represents a character.
• The root is empty.
• A null marker (*) denotes the end of a word.

Time complexity:

• Insertion: $O(L)$ (where $L$ = length of the string).
• Search: $O(L)$.
• Space: $O(N\times L)$ (worst case, where $N$ = number of words).

**2.2 Structure

Example: Words ["PATHO", "PSYCHO", "PATH"] stored in a Trie.

**2.3 Operations: Insert and Search

Insert("PATHO"):

1. Start at root, traverse P → A → T → H → O.
2. Add * at O to mark the end of the word.

Search("PSY"):

1. Traverse P → S → Y.
2. No * at Y → word not found.

Trace: Insert "PATH" into the Trie above

2.4 Applications

• Autocomplete: Google Search, eSewa’s transaction suggestions.
• Spell checkers: Dictionary lookups (e.g., Microsoft Word).
• IP routing: Longest prefix matching in networks (e.g., NTC’s routing tables).

In the real world:

• eSewa’s transaction autocomplete: As you type "electricity," the Trie quickly suggests "electricity bill payment" from stored transactions.
• Google Search: Uses Tries to rank and suggest search queries in milliseconds.
• Ncell’s USSD menu: The *123# menu system uses Tries to navigate options like "Balance Check" or "Data Plan."

3. Disjoint-Set Forests (Union-Find)

3.1 Definition

A disjoint-set data structure (Union-Find) manages a partition of elements into disjoint sets with two operations:

1. Find(x): Determine which subset x belongs to.
2. Union(x, y): Merge the subsets of x and y.

Optimizations:

• Path compression (Find): Flatten the structure for future queries.
• Union by rank: Attach the shorter tree to the root of the taller tree.

Time complexity:

• Near-$O(1)$ per operation (amortized, with optimizations).

**3.2 Structure

Example: Sets {2, 3}, {4, 5}, {6, 7}.

**3.3 Operations: Find and Union

Find(3):

1. Traverse 3 → 1 (root).
2. Path compression: Update 3 to point directly to 1.

Union(3, 4):

1. Find roots: 3 → 1, 4 → 2.
2. Union by rank: Attach 1 to 2 (assuming rank of 2 > rank of 1).

Trace: Union-Find with Path Compression

3.4 Applications

• Network connectivity: Detect cycles in graphs (e.g., NTC’s redundant fiber links).
• Social networks: Friend groups (e.g., Facebook’s friend suggestions).
• Kruskal’s algorithm: Builds MST by checking for cycles.

In the real world:

• NTC’s network redundancy: Union-Find ensures no loops are created when adding new fiber links between cities.
• Khalti’s fraud detection: Detects if two transactions are from the same "group" (e.g., linked accounts) to flag suspicious activity.
• Daraz’s inventory management: Groups products by supplier to optimize bulk orders.

4. Advanced Graph Algorithms

4.1 Minimum Spanning Tree (MST)

Kruskal’s Algorithm:

1. Sort all edges by weight.
2. Add edges one by one, skipping those that form cycles (checked with Union-Find).

Prim’s Algorithm:

1. Start with an arbitrary node.
2. Greedily add the cheapest edge from the current MST to a vertex outside it.

Comparison:

Trace: Kruskal’s on Graph with Edges (A-B:1), (B-C:2), (A-C:3), (C-D:4)

4.2 Shortest Path: Dijkstra’s Algorithm

Steps:

1. Initialize distances: dist[source] = 0, others ∞.
2. Use a priority queue (min-heap) to pick the next node.
3. Relax edges: Update distances if a shorter path is found.

Trace: Dijkstra’s from A to D (weights: A-B:1, B-C:2, A-C:3, C-D:4)

In the real world:

• Pathao’s route optimization: Dijkstra’s finds the fastest path from pickup to destination, avoiding traffic (e.g., Kathmandu’s busy Thapathali route).
• NTC’s internet routing: Shortest-path algorithms ensure data packets take the least time between servers.
• NEPSE’s stock dependency: Topological sorting resolves buy/sell dependencies between stocks (e.g., "Buy X after Y rises").

5. Topological Sorting

5.1 Definition

A linear ordering of vertices in a DAG such that for every directed edge (u → v), u comes before v.

Applications:

• Task scheduling (e.g., course prerequisites).
• Dependency resolution (e.g., software builds).

**5.2 Algorithm: Kahn’s Method

1. Compute in-degree (number of incoming edges) for each node.
2. Enqueue nodes with in-degree = 0.
3. For each node u dequeued, reduce in-degree of its neighbors. If a neighbor’s in-degree becomes 0, enqueue it.

Trace: Topological Sort for DAG (A→B, A→C, B→D, C→D)

5.3 Applications

• Course scheduling: TU’s BIM course prerequisites (e.g., "Take Data Structures before Algorithms").
• Software builds: Compile dependencies in the correct order (e.g., gcc for C programs).
• Project management: Task ordering in Trello or Asana.

In the real world:

• TU’s exam schedule: Topological sorting ensures no student writes an exam before its prerequisites are cleared.
• Daraz’s order fulfillment: Tasks like "pack → ship → deliver" must follow this order.
• Ncell’s app updates: Dependency resolution ensures new features rely on existing code.

Exam Tip

1. Heaps:

   • Memorize array indices for children/parent.
   • Practice insert/extract traces (show bubble-up/down steps).
   • Common pitfall: Forgetting to heapify after insertion/deletion.

2. Tries:

   • Draw the Trie structure for given words (e.g., ["CAT", "DOG", "CAR"]).
   • Explain autocomplete using prefix traversal.
   • Exam question: "How would you implement a spell checker using a Trie?"

3. Union-Find:

   • Path compression and union by rank are key optimizations—explain why they reduce time complexity.
   • Real-world link: NTC’s network redundancy or Khalti’s fraud detection.

4. Graph Algorithms:

   • Kruskal’s vs. Prim’s: Know when to use each (sparse vs. dense graphs).
   • Dijkstra’s: Always use a priority queue (min-heap). Trace the distance updates.
   • Topological sort: Kahn’s method is safer than DFS for cycles (but DFS is also acceptable if the graph is guaranteed to be a DAG).

5. Comparison Tables:

   • The exam often asks to compare data structures (e.g., "Heaps vs. BSTs for priority queues").
   • Key points:
     • Heaps: Faster insert/delete ($O(\log n)$), but no efficient search by key.
     • BSTs: $O(\log n)$ for all operations (if balanced), but slower insertions in worst case.

6. Pseudocode:

   • Write clear pseudocode for algorithms (e.g., Dijkstra’s with a priority queue).
   • Example:

     def dijkstra(graph, source):
         dist = {node: ∞ for node in graph}
         dist[source] = 0
         heap = [(0, source)]
         while heap:
             current_dist, u = heappop(heap)
             for v, weight in graph[u]:
                 if dist[v] > dist[u] + weight:
                     dist[v] = dist[u] + weight
                     heappush(heap, (dist[v], v))
         return dist
     

7. Real-World Scenarios:

   • Always relate to Nepalese examples (e.g., "How would Pathao use a min-heap?" or "How does NTC avoid network loops?").
   • Avoid vague answers: Instead of "used in databases," say "eSewa uses Tries for transaction autocomplete."

Final Advice:

• Draw diagrams for every algorithm (especially heap operations and graph traversals).
• Time complexity is critical—know $O(\log n)$ vs. $O(n\log n)$ trade-offs.
• Practice coding: Implement a heap or Trie in code (even pseudocode) to solidify understanding.