heap-typed v2.0.3

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

npm i heap-typed --save

yarn

yarn add heap-typed

snippet

Use Heap to sort an array

    function heapSort(arr: number[]): number[] {
      const heap = new Heap<number>(arr, { comparator: (a, b) => a - b });
      const sorted: number[] = [];
      while (!heap.isEmpty()) {
        sorted.push(heap.poll()!); // Poll minimum element
      }
      return sorted;
    }

    const array = [5, 3, 8, 4, 1, 2];
    console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8]

Use Heap to solve top k problems

    function topKElements(arr: number[], k: number): number[] {
      const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap
      arr.forEach(num => {
        heap.add(num);
        if (heap.size > k) heap.poll(); // Keep the heap size at K
      });
      return heap.toArray();
    }

    const numbers = [10, 30, 20, 5, 15, 25];
    console.log(topKElements(numbers, 3)); // [15, 10, 5]

Use Heap to merge sorted sequences

    function mergeSortedSequences(sequences: number[][]): number[] {
      const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], {
        comparator: (a, b) => a.value - b.value // Min heap
      });

      // Initialize heap
      sequences.forEach((seq, seqIndex) => {
        if (seq.length) {
          heap.add({ value: seq[0], seqIndex, itemIndex: 0 });
        }
      });

      const merged: number[] = [];
      while (!heap.isEmpty()) {
        const { value, seqIndex, itemIndex } = heap.poll()!;
        merged.push(value);

        if (itemIndex + 1 < sequences[seqIndex].length) {
          heap.add({
            value: sequences[seqIndex][itemIndex + 1],
            seqIndex,
            itemIndex: itemIndex + 1
          });
        }
      }

      return merged;
    }

    const sequences = [
      [1, 4, 7],
      [2, 5, 8],
      [3, 6, 9]
    ];
    console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

Use Heap to dynamically maintain the median

    class MedianFinder {
      private low: MaxHeap<number>; // Max heap, stores the smaller half
      private high: MinHeap<number>; // Min heap, stores the larger half

      constructor() {
        this.low = new MaxHeap<number>([]);
        this.high = new MinHeap<number>([]);
      }

      addNum(num: number): void {
        if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num);
        else this.high.add(num);

        // Balance heaps
        if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!);
        else if (this.high.size > this.low.size) this.low.add(this.high.poll()!);
      }

      findMedian(): number {
        if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2;
        return this.low.peek()!;
      }
    }

    const medianFinder = new MedianFinder();
    medianFinder.addNum(10);
    console.log(medianFinder.findMedian()); // 10
    medianFinder.addNum(20);
    console.log(medianFinder.findMedian()); // 15
    medianFinder.addNum(30);
    console.log(medianFinder.findMedian()); // 20
    medianFinder.addNum(40);
    console.log(medianFinder.findMedian()); // 25
    medianFinder.addNum(50);
    console.log(medianFinder.findMedian()); // 30

Use Heap for load balancing

    function loadBalance(requests: number[], servers: number): number[] {
      const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap
      const serverLoads = new Array(servers).fill(0);

      for (let i = 0; i < servers; i++) {
        serverHeap.add({ id: i, load: 0 });
      }

      requests.forEach(req => {
        const server = serverHeap.poll()!;
        serverLoads[server.id] += req;
        server.load += req;
        serverHeap.add(server); // The server after updating the load is re-entered into the heap
      });

      return serverLoads;
    }

    const requests = [5, 2, 8, 3, 7];
    console.log(loadBalance(requests, 3)); // [12, 8, 5]

Use Heap to schedule tasks

    type Task = [string, number];

    function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> {
      const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap
      const allocation = new Map<number, Task[]>();

      // Initialize the load on each machine
      for (let i = 0; i < machines; i++) {
        machineHeap.add({ id: i, load: 0 });
        allocation.set(i, []);
      }

      // Assign tasks
      tasks.forEach(([task, load]) => {
        const machine = machineHeap.poll()!;
        allocation.get(machine.id)!.push([task, load]);
        machine.load += load;
        machineHeap.add(machine); // The machine after updating the load is re-entered into the heap
      });

      return allocation;
    }

    const tasks: Task[] = [
      ['Task1', 3],
      ['Task2', 1],
      ['Task3', 2],
      ['Task4', 5],
      ['Task5', 4]
    ];
    const expectedMap = new Map<number, Task[]>();
    expectedMap.set(0, [
      ['Task1', 3],
      ['Task4', 5]
    ]);
    expectedMap.set(1, [
      ['Task2', 1],
      ['Task3', 2],
      ['Task5', 4]
    ]);
    console.log(scheduleTasks(tasks, 2)); // expectedMap

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards