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

php 
<?php
 
function buildTree(array $items, ?int $parentId = null): array
{

Building a tree from a flat list in PHP

recursion tree grouping
Intermediate 6 steps
typescript 
import { Injectable, signal, computed } from '@angular/core';
import {
  HttpInterceptorFn,
  HttpContextToken,

Tracking HTTP loading state in Angular

signals http-interceptor reference-counting
Intermediate 8 steps
typescript 
type Event = Record<string, unknown>;
 
interface BatcherOptions {
  endpoint: string;

Batching analytics events in TypeScript

batching buffering async
Intermediate 8 steps
typescript 
import { Injectable } from '@angular/core';
import { PreloadingStrategy, Route, Routes, RouterModule } from '@angular/router';
import { NgModule } from '@angular/core';
import { Observable, of, timer } from 'rxjs';

A custom preloading strategy in Angular

lazy-loading preloading rxjs
Intermediate 7 steps
java 
@Service
public class OrderMetricsService {
 
    private final MeterRegistry registry;

Instrumenting orders with Micrometer in Spring

metrics micrometer observability
Intermediate 8 steps
typescript 
import { Processor, WorkerHost, OnWorkerEvent } from '@nestjs/bullmq';
import { Logger } from '@nestjs/common';
import { Job } from 'bullmq';
import { MailerService } from '../mailer/mailer.service';

Processing background email jobs in NestJS

job-queue background-processing dependency-injection
Intermediate 7 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