What

Brief

This is a standalone Heap data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package

How

install

npm

1npm i heap-typed --save

yarn

1yarn add heap-typed

snippet

Use Heap to sort an array

1    function heapSort(arr: number[]): number[] {
2      const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });
3      const sorted: number[] = [];
4      while (!heap.isEmpty()) {
5        sorted.push(heap.poll()!); // Poll minimum element
6      }
7      return sorted;
8    }
9
10    const array = [5, 3, 8, 4, 1, 2];
11    console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8]

Use Heap to solve top k problems

1    function topKElements(arr: number[], k: number): number[] {
2      const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap
3      arr.forEach(num => {
4        heap.add(num);
5        if (heap.size > k) heap.poll(); // Keep the heap size at K
6      });
7      return heap.toArray();
8    }
9
10    const numbers = [10, 30, 20, 5, 15, 25];
11    console.log(topKElements(numbers, 3)); // [15, 10, 5]

Use Heap to merge sorted sequences

1    function mergeSortedSequences(sequences: number[][]): number[] {
2      const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {
3        comparator: (a, b) => a.value - b.value // Min heap
4      });
5
6      // Initialize heap
7      sequences.forEach((seq, seqIndex) => {
8        if (seq.length) {
9          heap.add({ value: seq[0], seqIndex, itemIndex: 0 });
10        }
11      });
12
13      const merged: number[] = [];
14      while (!heap.isEmpty()) {
15        const { value, seqIndex, itemIndex } = heap.poll()!;
16        merged.push(value);
17
18        if (itemIndex + 1 < sequences[seqIndex].length) {
19          heap.add({
20            value: sequences[seqIndex][itemIndex + 1],
21            seqIndex,
22            itemIndex: itemIndex + 1
23          });
24        }
25      }
26
27      return merged;
28    }
29
30    const sequences = [
31      [1, 4, 7],
32      [2, 5, 8],
33      [3, 6, 9]
34    ];
35    console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

Use Heap to dynamically maintain the median

1    class MedianFinder {
2      private low: MaxHeap<number>; // Max heap, stores the smaller half
3      private high: MinHeap<number>; // Min heap, stores the larger half
4
5      constructor() {
6        this.low = new MaxHeap<number>([]);
7        this.high = new MinHeap<number>([]);
8      }
9
10      addNum(num: number): void {
11        if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num);
12        else this.high.add(num);
13
14        // Balance heaps
15        if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!);
16        else if (this.high.size > this.low.size) this.low.add(this.high.poll()!);
17      }
18
19      findMedian(): number {
20        if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2;
21        return this.low.peek()!;
22      }
23    }
24
25    const medianFinder = new MedianFinder();
26    medianFinder.addNum(10);
27    console.log(medianFinder.findMedian()); // 10
28    medianFinder.addNum(20);
29    console.log(medianFinder.findMedian()); // 15
30    medianFinder.addNum(30);
31    console.log(medianFinder.findMedian()); // 20
32    medianFinder.addNum(40);
33    console.log(medianFinder.findMedian()); // 25
34    medianFinder.addNum(50);
35    console.log(medianFinder.findMedian()); // 30

Use Heap for load balancing

1    function loadBalance(requests: number[], servers: number): number[] {
2      const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap
3      const serverLoads = new Array(servers).fill(0);
4
5      for (let i = 0; i < servers; i++) {
6        serverHeap.add({ id: i, load: 0 });
7      }
8
9      requests.forEach(req => {
10        const server = serverHeap.poll()!;
11        serverLoads[server.id] += req;
12        server.load += req;
13        serverHeap.add(server); // The server after updating the load is re-entered into the heap
14      });
15
16      return serverLoads;
17    }
18
19    const requests = [5, 2, 8, 3, 7];
20    console.log(loadBalance(requests, 3)); // [12, 8, 5]

Use Heap to schedule tasks

1    type Task = [string, number];
2
3    function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {
4      const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap
5      const allocation = new Map<number, Task[]>();
6
7      // Initialize the load on each machine
8      for (let i = 0; i < machines; i++) {
9        machineHeap.add({ id: i, load: 0 });
10        allocation.set(i, []);
11      }
12
13      // Assign tasks
14      tasks.forEach(([task, load]) => {
15        const machine = machineHeap.poll()!;
16        allocation.get(machine.id)!.push([task, load]);
17        machine.load += load;
18        machineHeap.add(machine); // The machine after updating the load is re-entered into the heap
19      });
20
21      return allocation;
22    }
23
24    const tasks: Task[] = [
25      ['Task1', 3],
26      ['Task2', 1],
27      ['Task3', 2],
28      ['Task4', 5],
29      ['Task5', 4]
30    ];
31    const expectedMap = new Map<number, Task[]>();
32    expectedMap.set(0, [
33      ['Task1', 3],
34      ['Task4', 5]
35    ]);
36    expectedMap.set(1, [
37      ['Task2', 1],
38      ['Task3', 2],
39      ['Task5', 4]
40    ]);
41    console.log(scheduleTasks(tasks, 2)); // expectedMap

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Data Structure	Unit Test	Performance Test	API Docs
Heap			Heap

Standard library data structure comparison

Data Structure Typed	C++ STL	java.util	Python collections
Heap<E>	priority_queue<T>	PriorityQueue<E>	heapq

Benchmark

Built-in classic algorithms

Algorithm	Function Description	Iteration Type

Software Engineering Design Standards

Principle	Description
Practicality	Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names.
Extensibility	Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures.
Modularization	Includes data structure modularization and independent NPM packages.
Efficiency	All methods provide time and space complexity, comparable to native JS performance.
Maintainability	Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns.
Testability	Automated and customized unit testing, performance testing, and integration testing.
Portability	Plans for porting to Java, Python, and C++, currently achieved to 80%.
Reusability	Fully decoupled, minimized side effects, and adheres to OOP.
Security	Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects.
Scalability	Data structure software does not involve load issues.