0
# Heaps & Priority Queues
1

2
High-performance priority queue implementations for efficient minimum/maximum element access with logarithmic insertion and removal operations.
3

4
## Capabilities
5

6
### Basic Heap
7

8
Binary heap implementation providing O(log n) insertion and deletion with O(1) peek operations.
9

10
```typescript { .api }
11
/**
12
 * Binary heap (min-heap by default) with configurable comparison function
13
 * @param comparator Optional comparison function for custom ordering
14
 */
15
function Heap<T>(comparator?: (a: T, b: T) => number): Heap<T>;
16

17
interface Heap<T> {
18
  /** Number of items in the heap */
19
  readonly size: number;
20
  
21
  /** Add item to the heap, returns new size */
22
  push(item: T): number;
23
  
24
  /** Returns the minimum item without removing it */
25
  peek(): T | undefined;
26
  
27
  /** Removes and returns the minimum item */
28
  pop(): T | undefined;
29
  
30
  /** Pops heap then pushes new item, returns popped item */
31
  replace(item: T): T | undefined;
32
  
33
  /** Pushes item then pops heap, returns popped item */
34
  pushpop(item: T): T | undefined;
35
  
36
  /** Returns sorted array of all items (non-destructive) */
37
  toArray(): Array<T>;
38
  
39
  /** Returns sorted array and clears the heap */
40
  consume(): Array<T>;
41
  
42
  /** Removes all items from the heap */
43
  clear(): void;
44
  
45
  /** Returns representation for debugging */
46
  inspect(): any;
47
}
48
```
49

50
**Usage Examples:**
51

52
```typescript
53
import {Heap} from "mnemonist";
54

55
// Basic min-heap
56
const minHeap = new Heap<number>();
57
minHeap.push(5, 2, 8, 1, 9);
58
console.log(minHeap.peek()); // 1
59
console.log(minHeap.pop());  // 1
60
console.log(minHeap.size);   // 4
61

62
// Custom priority heap
63
interface Task { name: string; priority: number; }
64
const taskHeap = new Heap<Task>((a, b) => a.priority - b.priority);
65
taskHeap.push({name: "urgent", priority: 1});
66
taskHeap.push({name: "normal", priority: 5});
67
console.log(taskHeap.peek().name); // "urgent"
68

69
// Efficient operations
70
const item = minHeap.pushpop(3); // Push 3, then pop minimum
71
const replaced = minHeap.replace(7); // Pop minimum, then push 7
72
```
73

74
### Min Heap & Max Heap
75

76
Specialized heap variants for explicit minimum or maximum ordering.
77

78
```typescript { .api }
79
/**
80
 * Min-heap: smallest item at root (alias for default Heap behavior)
81
 */
82
function MinHeap<T>(comparator?: (a: T, b: T) => number): MinHeap<T>;
83

84
/**
85
 * Max-heap: largest item at root
86
 */
87
function MaxHeap<T>(comparator?: (a: T, b: T) => number): MaxHeap<T>;
88
```
89

90
**Usage Examples:**
91

92
```typescript
93
import {MinHeap, MaxHeap} from "mnemonist";
94

95
const minHeap = new MinHeap<number>();
96
const maxHeap = new MaxHeap<number>();
97

98
[5, 2, 8, 1, 9].forEach(n => {
99
  minHeap.push(n);
100
  maxHeap.push(n);
101
});
102

103
console.log(minHeap.peek()); // 1 (smallest)
104
console.log(maxHeap.peek()); // 9 (largest)
105
```
106

107
### Heap Static Methods
108

109
Factory methods on the Heap class.
110

111
```typescript { .api }
112
/**
113
 * Create heap from iterable (static method on Heap class)
114
 */
115
static from<T>(
116
  iterable: Iterable<T> | {[key: string]: T},
117
  comparator?: (a: T, b: T) => number
118
): Heap<T>;
119
```
120

121
### Heap Utility Functions
122

123
Standalone utility functions for finding k smallest/largest elements efficiently.
124

125
```typescript { .api }
126
/**
127
 * Find n smallest items from iterable using heap
128
 */
129
function nsmallest<T>(n: number, values: Iterable<T>): Array<T>;
130
function nsmallest<T>(
131
  comparator: (a: T, b: T) => number,
132
  n: number,
133
  values: Iterable<T>
134
): Array<T>;
135

136
/**
137
 * Find n largest items from iterable using heap
138
 */
139
function nlargest<T>(n: number, values: Iterable<T>): Array<T>;
140
function nlargest<T>(
141
  comparator: (a: T, b: T) => number,
142
  n: number,
143
  values: Iterable<T>
144
): Array<T>;
145
```
146

147
**Usage Examples:**
148

149
```typescript
150
import {Heap} from "mnemonist";
151

152
// Create from array
153
const heap = Heap.from([5, 2, 8, 1, 9]);
154
console.log(heap.peek()); // 1
155
```
156

157
**Usage Examples:**
158

159
```typescript
160
import {nsmallest, nlargest} from "mnemonist";
161

162
// Find smallest/largest items efficiently
163
const numbers = [15, 3, 8, 1, 12, 7, 4, 9];
164
const smallest3 = nsmallest(3, numbers); // [1, 3, 4]
165
const largest3 = nlargest(3, numbers);   // [15, 12, 9]
166

167
// With custom comparator
168
const people = [{name: "Alice", age: 30}, {name: "Bob", age: 25}];
169
const youngest2 = nsmallest((a, b) => a.age - b.age, 2, people);
170
```
171

172
### Fibonacci Heap
173

174
Advanced heap with better amortized time complexity for decrease-key operations.
175

176
```typescript { .api }
177
/**
178
 * Fibonacci heap providing O(1) amortized insertion and decrease-key
179
 * @param comparator Optional comparison function for custom ordering
180
 */
181
function FibonacciHeap<T>(comparator?: (a: T, b: T) => number): FibonacciHeap<T>;
182

183
interface FibonacciHeap<T> {
184
  /** Number of items in the heap */
185
  readonly size: number;
186
  
187
  /** Add item to the heap, returns new size */
188
  push(item: T): number;
189
  
190
  /** Returns the minimum item without removing it */
191
  peek(): T | undefined;
192
  
193
  /** Removes and returns the minimum item */
194
  pop(): T | undefined;
195
  
196
  /** Removes all items from the heap */
197
  clear(): void;
198
  
199
  /** Returns representation for debugging */
200
  inspect(): any;
201
}
202
```
203

204
**Usage Examples:**
205

206
```typescript
207
import {FibonacciHeap, MinFibonacciHeap, MaxFibonacciHeap} from "mnemonist";
208

209
// Basic fibonacci heap (min-heap)
210
const fibHeap = new FibonacciHeap<number>();
211
fibHeap.push(5, 2, 8, 1);
212
console.log(fibHeap.pop()); // 1
213

214
// Max fibonacci heap
215
const maxFibHeap = new MaxFibonacciHeap<number>();
216
maxFibHeap.push(5, 2, 8, 1);
217
console.log(maxFibHeap.pop()); // 8
218

219
// Create from iterable
220
const heap = FibonacciHeap.from([3, 1, 4, 1, 5]);
221
```
222

223
**Performance Notes:**
224
- Better for applications with many insertions and few deletions
225
- O(1) amortized insert vs O(log n) for binary heap
226
- O(log n) amortized delete-min (same as binary heap)
227
- More memory overhead than basic heap
228

229
### Fixed Reverse Heap
230

231
Fixed-capacity heap optimized for finding k smallest/largest items from streaming data.
232

233
```typescript { .api }
234
/**
235
 * Fixed-capacity heap that maintains k best items
236
 * @param ArrayClass Array constructor for backing storage
237
 * @param comparator Optional comparison function
238
 * @param capacity Maximum number of items to store
239
 */
240
function FixedReverseHeap<T>(
241
  ArrayClass: ArrayConstructor,
242
  comparator: (a: T, b: T) => number,
243
  capacity: number
244
): FixedReverseHeap<T>;
245

246
function FixedReverseHeap<T>(
247
  ArrayClass: ArrayConstructor,
248
  capacity: number
249
): FixedReverseHeap<T>;
250

251
interface FixedReverseHeap<T> {
252
  /** Maximum capacity of the heap */
253
  readonly capacity: number;
254
  
255
  /** Current number of items in the heap */
256
  readonly size: number;
257
  
258
  /** Add item if space available, or replace worst item if full */
259
  push(item: T): number;
260
  
261
  /** Returns sorted array and clears the heap */
262
  consume(): Array<T>;
263
  
264
  /** Returns sorted array (non-destructive) */
265
  toArray(): Array<T>;
266
  
267
  /** Removes all items from the heap */
268
  clear(): void;
269
  
270
  /** Returns representation for debugging */
271
  inspect(): any;
272
}
273
```
274

275
**Usage Examples:**
276

277
```typescript
278
import {FixedReverseHeap} from "mnemonist";
279

280
// Find 5 smallest numbers from stream
281
const kSmallest = new FixedReverseHeap(Array, 5);
282

283
// Process streaming data
284
[8, 3, 15, 1, 12, 7, 4, 9, 2, 11].forEach(num => {
285
  kSmallest.push(num);
286
});
287

288
console.log(kSmallest.toArray()); // [1, 2, 3, 4, 7] (5 smallest)
289

290
// Find largest items with custom comparator  
291
const kLargest = new FixedReverseHeap(
292
  Array,
293
  (a, b) => b - a, // Reverse comparator for largest
294
  3
295
);
296

297
[8, 3, 15, 1, 12].forEach(num => kLargest.push(num));
298
console.log(kLargest.toArray()); // [15, 12, 8] (3 largest)
299

300
// Using typed arrays for performance
301
const typedHeap = new FixedReverseHeap(Float32Array, 100);
302
```
303

304
**Performance Notes:**
305
- O(log k) insertion where k is capacity
306
- O(1) space beyond the k items stored
307
- Ideal for "top-k" problems with streaming data
308
- Automatically handles capacity management
309

310
### Low-Level Heap Operations
311

312
Direct array-based heap operations for advanced use cases.
313

314
```typescript { .api }
315
/**
316
 * Low-level heap operations on raw arrays
317
 */
318
namespace HeapOperations {
319
  function push<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): void;
320
  function pop<T>(comparator: (a: T, b: T) => number, heap: Array<T>): T;
321
  function replace<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): T;
322
  function pushpop<T>(comparator: (a: T, b: T) => number, heap: Array<T>, item: T): T;
323
  function heapify<T>(comparator: (a: T, b: T) => number, array: Array<T>): void;
324
  function consume<T>(comparator: (a: T, b: T) => number, heap: Array<T>): Array<T>;
325
}
326
```
327

328
## Types
329

330
```typescript { .api }
331
/**
332
 * Comparison function type used by all heap implementations
333
 * Should return: negative if a < b, zero if a === b, positive if a > b
334
 */
335
type HeapComparator<T> = (a: T, b: T) => number;
336

337
/**
338
 * Array constructor types supported by FixedReverseHeap
339
 */
340
type ArrayConstructor = 
341
  | ArrayConstructor
342
  | Int8ArrayConstructor
343
  | Uint8ArrayConstructor
344
  | Int16ArrayConstructor
345
  | Uint16ArrayConstructor
346
  | Int32ArrayConstructor
347
  | Uint32ArrayConstructor
348
  | Float32ArrayConstructor
349
  | Float64ArrayConstructor;
350
```
351

352
## Performance Characteristics
353

354
| Operation | Basic Heap | Fibonacci Heap | Fixed Reverse Heap |
355
|-----------|------------|----------------|-------------------|
356
| Insert | O(log n) | O(1) amortized | O(log k) |
357
| Extract Min | O(log n) | O(log n) amortized | N/A |
358
| Peek | O(1) | O(1) | N/A |
359
| Build from array | O(n) | O(n) | O(k log k) |
360
| Space | O(n) | O(n) | O(k) |
361
362
Where n is the total number of elements and k is the fixed capacity.
363

364
## Choosing the Right Heap
365

366
- **Basic Heap**: General-purpose priority queue with good performance
367
- **Fibonacci Heap**: When you need many insertions with occasional decreases of priorities
368
- **Fixed Reverse Heap**: For "top-k" problems or when memory is constrained
369
- **Max variants**: When you need largest-first ordering instead of smallest-first