@js-structure/heap

A high-performance heap data structure implementation for JavaScript/TypeScript, supporting both min-heap and max-heap.

Features

- 🚀 Generic support with full type safety
- 📦 Both min-heap and max-heap support
- 🔧 Custom comparator functions
- ⚡ High-performance heap operations
- 🔄 Iterator protocol support (for...of, spread operator)
- 🎯 Method chaining
- ✅ Comprehensive test coverage
- 📝 TypeScript type definitions

Installation

``bash
npm install @js-structure/heap
`

Quick Start

$3

`typescript
import Heap from '@js-structure/heap';

const minHeap = new Heap(Heap.MIN_HEAP);

minHeap.push(5).push(3).push(7).push(1);

console.log(minHeap.top()); // 1
console.log(minHeap.pop()); // 1
console.log(minHeap.pop()); // 3
`

$3

`typescript
const maxHeap = new Heap(Heap.MAX_HEAP);

maxHeap.push(5).push(3).push(7).push(1);

console.log(maxHeap.top()); // 7
console.log(maxHeap.pop()); // 7
`

$3

`typescript
const heap = new Heap(Heap.MIN_HEAP, [5, 3, 7, 1, 9, 2]);
heap.balance(); // Balance the heap

console.log(heap.top()); // 1
`

$3

`typescript
interface Task {
name: string;
priority: number;
}

const taskHeap = new Heap(
(a, b) => a.priority < b.priority,
[
{ name: 'task1', priority: 5 },
{ name: 'task2', priority: 1 },
{ name: 'task3', priority: 3 }
]
);

taskHeap.balance();
console.log(taskHeap.top()); // { name: 'task2', priority: 1 }
`

API

$3

`typescript
constructor(comparator: (a: T, b: T) => boolean, value?: T[])
`

Creates a new heap instance.

- comparator: Comparison function, returns true if first argument should be closer to the top
- value: Optional initial values array

$3

- Heap.MIN_HEAP - Built-in min-heap comparator
- Heap.MAX_HEAP - Built-in max-heap comparator

$3

#### push(value: T): Heap

Adds an element to the heap and maintains heap property.

`typescript
heap.push(5).push(3).push(7);
`

#### pop(): T | null

Removes and returns the top element. Returns null if heap is empty.

`typescript
const value = heap.pop();
`

#### top(): T | null

Returns the top element without removing it. Returns null if heap is empty.

`typescript
const value = heap.top();
`

#### isEmpty(): boolean

Checks if the heap is empty.

#### size(): number

Returns the number of elements in the heap.

#### clear(): Heap

Removes all elements from the heap.

#### clone(): Heap

Creates a copy of the heap.

#### isValid(): boolean

Checks if the heap satisfies the heap property.

#### balance(): Heap

Balances the heap. Call this method after creating a heap from an array.

`typescript
const heap = new Heap(Heap.MIN_HEAP, [5, 3, 7, 1]);
heap.balance();
`

#### toArray(): T[]

Returns an array representation of the heap.

$3

The heap implements the iterator protocol and can be used with for...of loops and spread operators.

Note: Iteration consumes the heap elements (calls pop()), leaving the heap empty.

`typescript
const heap = new Heap(Heap.MIN_HEAP, [5, 3, 7, 1, 9]);
heap.balance();

for (const value of heap) {
console.log(value); // Output in order: 1, 3, 5, 7, 9
}

// Using spread operator
const heap2 = new Heap(Heap.MAX_HEAP, [5, 3, 7, 1]);
heap2.balance();
const sorted = [...heap2]; // [7, 5, 3, 1]
`

Use Cases

$3

`typescript
interface Job {
id: string;
priority: number;
task: () => void;
}

const jobQueue = new Heap(
(a, b) => a.priority > b.priority
);

jobQueue.push({ id: '1', priority: 5, task: () => console.log('Job 1') });
jobQueue.push({ id: '2', priority: 10, task: () => console.log('Job 2') });

while (!jobQueue.isEmpty()) {
const job = jobQueue.pop();
job?.task();
}
`

$3

`typescript
function topK(arr: number[], k: number): number[] {
const minHeap = new Heap(Heap.MIN_HEAP);

for (const num of arr) {
if (minHeap.size() < k) {
minHeap.push(num);
} else if (minHeap.top()! < num) {
minHeap.pop();
minHeap.push(num);
}
}

return minHeap.toArray();
}

console.log(topK([3, 1, 5, 9, 2, 7, 4, 8, 6], 3)); // [7, 8, 9]
`

$3

`typescript
function heapSort(arr: number[]): number[] {
const heap = new Heap(Heap.MIN_HEAP, arr);
heap.balance();

return [...heap]; // Uses iterator
}

console.log(heapSort([5, 3, 7, 1, 9, 2])); // [1, 2, 3, 5, 7, 9]
`

Complexity

| Operation | Time Complexity |
|-----------|----------------|
| push() | O(log n) |
| pop() | O(log n) |
| top() | O(1) |
| isEmpty() | O(1) |
| size() | O(1) |
| balance() | O(n) |
| clone() | O(n) |
| toArray() | O(n) |
| isValid()` | O(n) |

Space Complexity: O(n)