2.0.3 • Published 7 months ago

heap-typed v2.0.3

Weekly downloads
-
License
MIT
Repository
github
Last release
7 months ago

NPM GitHub top language npm eslint npm bundle size npm bundle size npm

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

1.52.9

11 months ago

2.0.3

7 months ago

2.0.1

8 months ago

2.0.0

10 months ago

1.53.4

10 months ago

1.53.3

10 months ago

1.53.6

10 months ago

1.53.5

10 months ago

1.53.8

10 months ago

1.53.7

10 months ago

1.53.9

10 months ago

1.54.3

10 months ago

1.54.2

10 months ago

1.53.0

11 months ago

1.53.2

10 months ago

1.53.1

11 months ago

1.54.1

10 months ago

1.54.0

10 months ago

1.52.8

11 months ago

1.52.5

11 months ago

1.52.6

11 months ago

1.52.4

12 months ago

1.52.3

1 year ago

1.52.2

1 year ago

1.52.1

1 year ago

1.52.0

2 years ago

1.51.9

2 years ago

1.51.8

2 years ago

1.51.7

2 years ago

1.51.5

2 years ago

1.51.4

2 years ago

1.51.3

2 years ago

1.51.0

2 years ago

1.51.2

2 years ago

1.51.1

2 years ago

1.50.9

2 years ago

1.50.8

2 years ago

1.50.7

2 years ago

1.50.6

2 years ago

1.50.5

2 years ago

1.50.4

2 years ago

1.50.3

2 years ago

1.50.2

2 years ago

1.50.1

2 years ago

1.50.0

2 years ago

1.49.9

2 years ago

1.49.8

2 years ago

1.49.5

2 years ago

1.49.7

2 years ago

1.49.6

2 years ago

1.49.4

2 years ago

1.49.3

2 years ago

1.49.2

2 years ago

1.49.1

2 years ago

1.49.0

2 years ago

1.48.6

2 years ago

1.48.5

2 years ago

1.48.8

2 years ago

1.48.7

2 years ago

1.48.9

2 years ago

1.37.0

2 years ago

1.37.3

2 years ago

1.37.4

2 years ago

1.37.2

2 years ago

1.37.7

2 years ago

1.37.8

2 years ago

1.37.5

2 years ago

1.37.6

2 years ago

1.37.9

2 years ago

1.40.0

2 years ago

1.44.0

2 years ago

1.44.1

2 years ago

1.48.0

2 years ago

1.48.2

2 years ago

1.48.1

2 years ago

1.48.4

2 years ago

1.48.3

2 years ago

1.38.2

2 years ago

1.38.0

2 years ago

1.38.1

2 years ago

1.38.6

2 years ago

1.38.7

2 years ago

1.38.4

2 years ago

1.38.5

2 years ago

1.38.8

2 years ago

1.38.9

2 years ago

1.41.1

2 years ago

1.41.0

2 years ago

1.41.3

2 years ago

1.41.2

2 years ago

1.45.1

2 years ago

1.41.5

2 years ago

1.45.0

2 years ago

1.41.4

2 years ago

1.45.3

2 years ago

1.41.7

2 years ago

1.45.2

2 years ago

1.41.6

2 years ago

1.41.9

2 years ago

1.41.8

2 years ago

1.39.1

2 years ago

1.39.2

2 years ago

1.39.0

2 years ago

1.39.5

2 years ago

1.39.6

2 years ago

1.39.3

2 years ago

1.39.4

2 years ago

1.42.0

2 years ago

1.42.2

2 years ago

1.42.1

2 years ago

1.42.4

2 years ago

1.42.3

2 years ago

1.46.2

2 years ago

1.42.6

2 years ago

1.46.1

2 years ago

1.42.5

2 years ago

1.42.8

2 years ago

1.46.3

2 years ago

1.42.7

2 years ago

1.46.6

2 years ago

1.46.5

2 years ago

1.42.9

2 years ago

1.46.8

2 years ago

1.46.7

2 years ago

1.36.4

2 years ago

1.36.5

2 years ago

1.36.2

2 years ago

1.36.3

2 years ago

1.36.8

2 years ago

1.36.9

2 years ago

1.36.6

2 years ago

1.43.1

2 years ago

1.43.0

2 years ago

1.43.3

2 years ago

1.47.1

2 years ago

1.47.3

2 years ago

1.47.2

2 years ago

1.47.5

2 years ago

1.47.4

2 years ago

1.47.7

2 years ago

1.47.6

2 years ago

1.47.9

2 years ago

1.47.8

2 years ago

1.35.1

2 years ago

1.34.2

2 years ago

1.34.3

2 years ago

1.32.2

2 years ago

1.35.0

2 years ago

1.34.1

2 years ago

1.34.6

2 years ago

1.33.7

2 years ago

1.34.7

2 years ago

1.33.8

2 years ago

1.32.9

2 years ago

1.40.0-rc

2 years ago

1.34.4

2 years ago

1.34.5

2 years ago

1.33.6

2 years ago

1.34.8

2 years ago

1.34.9

2 years ago

1.3.3

2 years ago

1.3.2

2 years ago

1.3.1

2 years ago

1.21.0

2 years ago

1.21.4

2 years ago

1.21.2

2 years ago

1.21.3

2 years ago

1.32.0

2 years ago

1.31.0

2 years ago

1.20.0

2 years ago

1.19.9

2 years ago

1.19.7

2 years ago

1.19.6

2 years ago

1.19.5

2 years ago

1.19.3

2 years ago