expand heap data structure for javascript
npm install @js-structure/heapA high-performance heap data structure implementation for JavaScript/TypeScript, supporting both min-heap and max-heap.
- 🚀 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
``bash`
npm install @js-structure/heap
`typescript
import Heap from '@js-structure/heap';
const minHeap = new 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
`
`typescript
const maxHeap = new Heap
maxHeap.push(5).push(3).push(7).push(1);
console.log(maxHeap.top()); // 7
console.log(maxHeap.pop()); // 7
`
`typescript
const heap = new Heap
heap.balance(); // Balance the heap
console.log(heap.top()); // 1
`
`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 }
`
`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 topvalue
- : Optional initial values array
- Heap.MIN_HEAP - Built-in min-heap comparatorHeap.MAX_HEAP
- - Built-in max-heap comparator
#### 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.
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]
`
`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();
}
`
`typescript
function topK(arr: number[], k: number): number[] {
const minHeap = new 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]
`
`typescript
function heapSort(arr: number[]): number[] {
const heap = new Heap
heap.balance();
return [...heap]; // Uses iterator
}
console.log(heapSort([5, 3, 7, 1, 9, 2])); // [1, 2, 3, 5, 7, 9]
`
| 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)