typescript 54 lines · 9 steps

Building a binary-heap priority queue in TypeScript

A generic min-heap that keeps the lowest-priority item ready at the front through bubble-up and bubble-down.

Explained by highlit
Intermediate binary-heap priority-queue generics data-structures algorithms
1export class PriorityQueue<T> {
2 private heap: Array<{ value: T; priority: number }> = [];
3 
4 get size(): number {
5 return this.heap.length;
6 }
7 
8 peek(): T | undefined {
9 return this.heap[0]?.value;
10 }
11 
12 enqueue(value: T, priority: number): void {
13 this.heap.push({ value, priority });
14 this.bubbleUp(this.heap.length - 1);
15 }
16 
17 dequeue(): T | undefined {
18 if (this.heap.length === 0) return undefined;
19 const top = this.heap[0];
20 const last = this.heap.pop()!;
21 if (this.heap.length > 0) {
22 this.heap[0] = last;
23 this.bubbleDown(0);
24 }
25 return top.value;
26 }
27 
28 private bubbleUp(index: number): void {
29 while (index > 0) {
30 const parent = (index - 1) >> 1;
31 if (this.heap[index].priority >= this.heap[parent].priority) break;
32 this.swap(index, parent);
33 index = parent;
34 }
35 }
36 
37 private bubbleDown(index: number): void {
38 const n = this.heap.length;
39 while (true) {
40 const left = index * 2 + 1;
41 const right = left + 1;
42 let smallest = index;
43 if (left < n && this.heap[left].priority < this.heap[smallest].priority) smallest = left;
44 if (right < n && this.heap[right].priority < this.heap[smallest].priority) smallest = right;
45 if (smallest === index) break;
46 this.swap(index, smallest);
47 index = smallest;
48 }
49 }
50 
51 private swap(a: number, b: number): void {
52 [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
53 }
54}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A binary heap stores a tree in a flat array, using index arithmetic to find parents and children.
  2. 2Insertion and removal both cost O(log n) because an item only travels the height of the tree.
  3. 3Sifting up on enqueue and down on dequeue is what preserves the heap ordering invariant.

Related explainers

typescript 
import { registerLocaleData } from '@angular/common';
import localeFr from '@angular/common/locales/fr';
import localeFrExtra from '@angular/common/locales/extra/fr';
import localeDe from '@angular/common/locales/de';

Locale-aware bootstrapping in Angular

i18n localization dependency-injection
Intermediate 8 steps
typescript 
import { Module } from '@nestjs/common';
import { ConfigModule } from '@nestjs/config';
import * as Joi from 'joi';
 

Validating env config at boot in NestJS

configuration schema-validation environment-variables
Intermediate 8 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
typescript 
import { Inject, Injectable, Logger } from '@nestjs/common';
import { CACHE_MANAGER } from '@nestjs/cache-manager';
import { Cache } from 'cache-manager';
import { InjectRepository } from '@nestjs/typeorm';

A cache-aside country lookup in NestJS

cache-aside dependency-injection batch-lookup
Intermediate 8 steps
typescript 
import { Injectable, effect, signal, computed } from '@angular/core';
 
interface Preferences {
  theme: 'light' | 'dark';

A signal-based preferences store in Angular

signals state-management persistence
Intermediate 7 steps
typescript 
import { useEffect, useState } from "react";
 
interface Section {
  id: string;

Building a scroll-spy hook in React

custom-hooks intersectionobserver dom-observation
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Building a binary-heap priority queue in TypeScript — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code