DSA DSA In Depth
0%
From-Scratch Build

Indexed d-ary Priority Queue with O(log_d N) Decrease-Key

Sedgewick’s Indexed d-ary Min-Priority Queue maintaining bidirectional heap/key position maps for O(1) lookup and O(log_d N) decreaseKey and arbitrary deletion.

~30 min Intermediate Lessons: Build Lab: Indexed 4-Ary Min/Max Priority Queue with O(log_d N) decreaseKey, Binary & d-ary Heaps: Floyd's O(N) Bottom-Up Build-Heap Proof, Dijkstra's Algorithm: Non-Negative Edge Invariant, Priority Queue Tradeoffs & Dial's Bucket Queue, Production Case Study: Hierarchical Hashed Timer Wheels vs Four-Heap Timers (Go runtime, Kafka, Linux), Mergeable Priority Queues: Leftist, Skew, Binomial & Fibonacci Heaps (O(1) Decrease-Key), Priority Queue Patterns: Running Median (Two Heaps), K-Way Merge & Top-K
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Overview

Sedgewick’s Indexed d-ary Min-Priority Queue maintaining bidirectional heap/key position maps for O(1) lookup and O(log_d N) decreaseKey and arbitrary deletion.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: d-ary Heap Geometry & Bidirectional Swap

  • Core Mechanical Concept: 0-Indexed d-ary Parent/Child Arithmetic & Synchronized pq[]/qp[] Maps
  • Target Module: index.js (IndexedDaryMinPQ._parent / _firstChild / _swap)
  • Engineering Specification: Implement _parent(pos), _firstChild(pos), and _swap(i, j). In a 0-indexed $d$-ary heap: - _parent(pos) = Math.floor((pos - 1) / this.d) - _firstChild(pos) = pos * this.d + 1 - this.qp[this.pq[pos]] === pos must hold for every 0 <= pos < this._size.
  • Verification Invariant: maintains bidirectional pq and qp bijection across swaps

Step 2: d-ary _siftUp and _siftDown

  • Core Mechanical Concept: Fast O(log_d N) Sift-Up vs d-Child Cache-Line Scan on Sift-Down
  • Target Module: index.js (IndexedDaryMinPQ._siftUp / _siftDown)
  • Engineering Specification: Implement _siftUp(pos) and _siftDown(pos). In _siftDown(pos), inspect children first = pos * d + 1 through Math.min(size - 1, first + d - 1), find minChild, and swap if _less(minChild, pos).
  • Verification Invariant: restores d-ary heap order via siftUp and siftDown

Step 3: Indexed Insert and popMin

  • Core Mechanical Concept: Root Extraction & Inverse Index Cleanup
  • Target Module: index.js (IndexedDaryMinPQ.insert / popMin)
  • Engineering Specification: Implement insert(id, priority) and popMin(). In popMin(), swap root 0 with size - 1, decrement _size, mark qp[minId] = -1, clear keys[minId] = undefined, and _siftDown(0) if non-empty.
  • Verification Invariant: inserts and extracts minimum elements in priority order

Step 4: O(log_d N) updateKey and Arbitrary Deletion

  • Core Mechanical Concept: Jumping Directly to Heap Position via qp[id]
  • Target Module: index.js (IndexedDaryMinPQ.updateKey / delete)
  • Engineering Specification: Implement updateKey(id, newPriority) and delete(id). Because pos = this.qp[id] gives the exact heap slot in $O(1)$, updating or deleting an arbitrary key requires only _siftUp(pos) and _siftDown(pos).
  • Verification Invariant: updates priorities and deletes arbitrary internal keys in O(log_d N)

Asymptotic & Memory Layout Guarantees

  • Category: Trees & Priority Queues
  • Difficulty: Intermediate (~30 minutes)
  • Key Architectural Highlights:
    • Configurable arity d (default d=4) reducing siftUp height by log2(d) and grouping children into one cache line
    • Bidirectional index maps pq[] and qp[] supporting O(1) contains(id) and O(log_d N) updateKey/delete
    • Zero duplicate heap entries during Dijkstra and Prim edge relaxations
  • Tags & Primitives: Indexed Priority Queue, d-ary Heap, Decrease-Key, Cache Line Alignment, Dijkstra

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.