Priority Queues & Advanced Topics: Heaps, D-Agendas, Event Scheduling

1. Priority Queues: Core Concepts

A priority queue (PQ) is a linear data structure where each element has a priority (integer or custom key), and operations retrieve/remove the highest-priority element first. Unlike standard queues (FIFO), PQs enforce order by priority, not insertion order.

Key Operations

Priority Queue vs. Standard Queue

flowchart TD
    A["Standard Queue (FIFO)"] -->|"Order"| B["Insertion Order"]
    C["Priority Queue"] -->|"Order"| D["Priority Key"]
    B -->|"Example"| E["Bank teller line: Customer 1 → Customer 2 → Customer 3"]
    D -->|"Example"| F["NTC call center: Urgent calls (priority 1) → Normal (priority 2)"]

2. Implementing Priority Queues

Array-Based Implementation

• Store elements in an unsorted array and scan for the max on every deleteMax().
  • Pros: Simple to code.
  • Cons: deleteMax() is O(n) (inefficient for large n).

Heap-Based Implementation (Optimal)

A binary heap is a complete binary tree where:

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

Visual: Max-Heap Structure

        [100] (Root)
       /      \
   [50]       [30]
  /   \      /   \
[20] [15] [25] [10]

• Heap Property: Every parent ≥ its children.
• Complete Tree: All levels filled left-to-right, except possibly the last (filled top-down).

Why Heaps?

• insert() and deleteMax() are O(log n) (vs. O(n) for arrays).
• Used in Dijkstra’s algorithm, Huffman coding, and operating system task scheduling.

3. Heap Operations (Traced Examples)

(a) Insertion into a Max-Heap

Example: Insert 40 into the heap above.

1. Add 40 as the new leaf (last position).

        [100]
       /      \
   [50]       [30]
     /   \      /   \
   [20] [15] [25] [10]
            \
            [40]
   

2. Heapify-Up: Compare 40 with its parent (25). Since 40 > 25, swap.

        [100]
       /      \
   [50]       [30]
     /   \      /   \
   [20] [15] [40] [10]
            /
          [25]
   

3. Compare 40 with new parent (30). Swap again.

        [100]
       /      \
   [50]       [40]
     /   \      /   \
   [20] [15] [30] [10]
            /
          [25]
   

4. Stop: 40 ≤ parent (50). Heap property restored.

Code Trace (Python-like Pseudocode)

def insert_heap(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0 and heap[(i-1)//2] < heap[i]:
        heap[i], heap[(i-1)//2] = heap[(i-1)//2], heap[i]
        i = (i-1)//2

Table: Variable States

(b) DeleteMax from a Max-Heap

Example: Delete the root (100) from the heap above.

1. Remove root (100), replace with last leaf (10), and reduce heap size.

        [10]
       /      \
   [50]       [30]
     /   \      /   \
   [20] [15] [40] [ ]
   

2. Heapify-Down: Compare 10 with children (50 and 30). Swap with 50.

        [50]
       /      \
   [10]       [30]
     /   \      /   \
   [20] [15] [40] [ ]
   

3. Compare 10 with new children (20 and 15). Swap with 20.

        [50]
       /      \
   [20]       [30]
     /   \      /   \
   [10] [15] [40] [ ]
   

4. Compare 10 with children (15 and 40). Swap with 40.

        [50]
       /      \
   [20]       [40]
     /   \      /   \
   [10] [15] [30] [ ]
   

5. Compare 10 with children (15 and 30). Swap with 30.

        [50]
       /      \
   [20]       [30]
     /   \      /   \
   [10] [15] [40] [ ]
   

6. Stop: 10 ≤ both children (15 and 40).

Code Trace

def delete_max(heap):
    if not heap: return None
    max_val = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    i = 0
    while True:
        left = 2*i + 1
        right = 2*i + 2
        largest = i
        if left < len(heap) and heap[left] > heap[largest]: largest = left
        if right < len(heap) and heap[right] > heap[largest]: largest = right
        if largest == i: break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest
    return max_val

Table: Variable States

4. Priority Queue Variants

(a) Circular Queue

A fixed-size queue where the end wraps around to the start after the last position. Use Case: NTC call center with a limited number of agents (e.g., 10). Calls are prioritized by urgency but must wait in a loop if all agents are busy.

Visual: Circular Queue (Size 5)

Index: 0  1  2  3  4
       |  |  |  |  |
Data:  [A][B][C][D][E] (front=0, rear=4)

• Enqueue: If rear == size-1, set rear = 0.
• Dequeue: If front == rear, queue is empty. Else, front = (front + 1) % size.

Example Trace

(b) Double-Ended Queue (Deque)

A queue with insertions/deletions at both ends. Use Case: Pathao driver scheduling—drivers can be added/removed from the start (new drivers) or end (experienced drivers) of the queue.

Operations

Visual: Deque Operations

flowchart TD
    A["Initial Deque: [ ]"] --> B["addFront(10): [10]"]
    B --> C["addRear(20): [10, 20]"]
    C --> D["removeFront(): [20]"]
    D --> E["addFront(5): [5, 20]"]
    E --> F["removeRear(): [5]"]

5. Advanced Applications

(a) Dijkstra’s Algorithm (Shortest Path)

Use Case: Google Maps finds the fastest route from Kathmandu to Pokhara by prioritizing edges with the lowest weight (time/distance).

Priority Queue Role: A min-heap stores unvisited nodes, always extracting the node with the smallest tentative distance.

Example Graph

        A
       /|\
      1 3 2
     / \/ \
    B  C  D

• Priority Queue: Initially {(A,0)}.
• Steps:
  1. Extract A (distance=0). Update neighbors:
     • B: 1, C: 3, D: 2.
     • PQ: {(B,1), (D,2), (C,3)}.
  2. Extract B (distance=1). Update C via B (distance=1+3=4 > current 3). No change.
     • PQ: {(D,2), (C,3)}.
  3. Extract D (distance=2). Update C via D (distance=2+2=4 > current 3). No change.
     • PQ: {(C,3)}.
  4. Extract C (distance=3). Done.

Shortest Paths: A→B (1), A→D (2), A→C (3).

(b) Event Scheduling (Operating Systems)

Use Case: NEPSE stock trading—trades are processed in order of priority (e.g., limit orders before market orders).

Priority Queue: A max-heap prioritizes higher-priority events (e.g., urgent trades).

flowchart TD
  A["Max-Heap (Priority Queue)"] --> B["Insert: Trade1 (priority=5)"]
  B --> C["Heap State: [5, 3, null, null, null]"]
  C --> D["Insert: Trade2 (priority=3)"]
  D --> E["Heap State: [5, 3, null, null, null] (after heapify)"]
  E --> F["PeekMax: Trade1 (priority=5)"]
  F --> G["DeleteMax: Trade1 removed"]
  G --> H["Heap State: [3, null, null, null, null] (after heapify)"]
  H --> I["PeekMax: Trade2 (priority=3)"]

6. Comparison Table: Priority Queue Implementations

7. Time and Space Complexity

Real-World Impact:

• NEPSE: Uses priority queues to handle stock order prioritization (e.g., limit orders before market orders).
• Daraz: Orders are prioritized by shipping urgency (e.g., same-day vs. next-day).
• NTC Call Center: Calls are queued by priority (urgent medical calls first).

In the Real World

1. NTC Call Center Queue

   • Idea: Priority Queue (Max-Heap).
   • How: Calls are assigned a priority (e.g., 1 for urgent, 2 for normal). The heap ensures urgent calls are handled first.
   • Example: If 5 urgent calls (priority=1) and 10 normal calls (priority=2) arrive, the heap processes all urgent calls before any normal ones.

2. Daraz Order Prioritization

   • Idea: Priority Queue (Min-Heap).
   • How: Orders are prioritized by delivery time (e.g., same-day orders have higher priority than next-day). The heap ensures faster deliveries are processed first.
   • Worked Example:
     • Orders: [Order1 (same-day), Order2 (next-day), Order3 (same-day)].
     • Priority: same-day=1, next-day=2.
     • Heap: {(Order1,1), (Order3,1), (Order2,2)}.
     • Processed in order: Order1, Order3, Order2.

3. NEPSE Stock Trading

   • Idea: Priority Queue (Max-Heap for Limit Orders).
   • How: Limit orders (e.g., "Buy at ₹100") are prioritized over market orders (e.g., "Buy now"). The heap ensures limit orders are matched first.
   • Worked Example:
     • Orders: [LimitOrder1 (price=₹100), MarketOrder1, LimitOrder2 (price=₹95)].
     • Heap: {(LimitOrder1,100), (LimitOrder2,95), (MarketOrder1,0)}.
     • Processed in order: LimitOrder1, LimitOrder2, MarketOrder1.

Exam Tip

1. Define Clearly:

   • Always start with: "A priority queue is a linear data structure where elements are served based on priority rather than insertion order."
   • For circular queue, mention: "A fixed-size queue where insertion/deletion wraps around to the start after the last position."

2. Visualize Heaps:

   • Draw the heap structure before/after operations (insert/delete). Label parent/child relationships.
   • For Dijkstra’s, show the priority queue state after each extraction.

3. Compare Implementations:

   • Highlight time complexity differences (e.g., heap’s O(log n) vs. array’s O(n) for deleteMax).
   • Mention real-world trade-offs (e.g., heap’s memory overhead vs. speed).

4. Application Focus:

   • Link to Nepal-specific examples (NTC, Daraz, NEPSE) to stand out. Use traced examples (like the Dijkstra’s path) to show step-by-step logic.
   • For circular queues, describe a scenario with fixed capacity (e.g., 10 NTC agents).

5. Code Snippets:

   • Include pseudocode for heap operations (insert, deleteMax) and trace it with a table of variable states.
   • Avoid complex syntax; focus on logic (e.g., heapify-up/down).

6. Avoid Common Mistakes:

   • Don’t confuse priority queue with standard queue (FIFO vs. priority-based).
   • For heaps, ensure the complete tree property is maintained after operations.
   • In Dijkstra’s, clarify that the priority queue stores unvisited nodes with tentative distances.

Key Formula to Remember

• Heapify-Up/Down: For a node at index i, its parent is at (i-1)//2, left child at 2i+1, right child at 2i+2.
• Circular Queue Wrap-Around: front = (front + 1) % size.