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 { useState, useEffect, useRef, useCallback } from "react";
 
interface Suggestion {
  id: string;

A debounced autocomplete hook in React

debounce custom-hooks abortcontroller
Advanced 7 steps
rust 
use axum::body::Bytes;
use axum::http::{header, HeaderValue, StatusCode};
use axum::response::{IntoResponse, Response};
use serde::Serialize;

Custom Axum responses with per-user ETags

etag trait-implementation generics
Intermediate 7 steps
typescript 
import { Body, Controller, Ip, Post, UnauthorizedException } from '@nestjs/common';
import { Throttle, ThrottlerGuard } from '@nestjs/throttler';
import { UseGuards } from '@nestjs/common';
import { AuthService } from './auth.service';

Rate-limiting an auth flow in NestJS

rate-limiting authentication guards
Intermediate 8 steps
typescript 
import { Component, computed, DestroyRef, inject, input, output, signal } from '@angular/core';
import { takeUntilDestroyed } from '@angular/core/rxjs-interop';
import { interval, map, takeWhile } from 'rxjs';
 

How a signal-driven countdown works in Angular

signals reactivity rxjs
Intermediate 8 steps
typescript 
type TokenType = "keyword" | "string" | "comment" | "number" | "text";
 
interface Token {
  type: TokenType;

How a regex tokenizer highlights code

tokenizer regex lexing
Intermediate 10 steps
typescript 
import { Component, inject, signal } from '@angular/core';
import { CdkDragDrop, DragDropModule, moveItemInArray } from '@angular/cdk/drag-drop';
import { HttpClient } from '@angular/common/http';
import { finalize } from 'rxjs';

Drag-and-drop reordering with signals in Angular

drag-and-drop signals optimistic-update
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