# Heaps

Priority queue implementations backed by the `Heap<T>` interface. A heap is a partially ordered tree where the root is always the minimum (or maximum) element according to the provided `CompareFn<T>`.

## Implementations

### BinaryHeap

Array-backed binary heap. The most common general-purpose heap.

| Operation | Best | Average        | Worst    |
| :-------- | :--- | :------------- | :------- |
| Space     | O(n) | O(n)           | O(n)     |
| `push`    | O(1) | O(1) amortized | O(log n) |
| `peek`    | O(1) | O(1)           | O(1)     |
| `pop`     | O(1) | O(log n)       | O(log n) |
| `has`     | O(1) | O(n)           | O(n)     |
| `delete`  | O(n) | O(n)           | O(n)     |
| `pushAll` | O(n) | O(n)           | O(n)     |
| `pushPop` | O(1) | O(log n)       | O(log n) |

**Strengths:** Cache-friendly (contiguous array), fast constant-factor `push`/`pop`, low memory overhead.

**Weaknesses:** `pushAll` (merge) requires O(n) rebuild; `delete` and `has` require linear scan.

### SkewHeap

Tree-based self-adjusting heap. All mutating operations reduce to a single merge primitive.

| Operation | Best | Average            | Worst |
| :-------- | :--- | :----------------- | :---- |
| Space     | O(n) | O(n)               | O(n)  |
| `push`    | O(1) | O(log n) amortized | O(n)  |
| `peek`    | O(1) | O(1)               | O(1)  |
| `pop`     | O(1) | O(log n) amortized | O(n)  |
| `has`     | O(1) | O(log n) pruned    | O(n)  |
| `delete`  | O(1) | O(log n) amortized | O(n)  |
| `pushAll` | O(1) | O(log n) amortized | O(n)  |
| `pushPop` | O(1) | O(log n) amortized | O(n)  |

**Strengths:** O(log n) amortized `pushAll` (merge) — significantly faster than BinaryHeap for merging. Efficient cross-heap merge when heaps share the same comparator reference.

**Weaknesses:** Pointer-based (not cache-friendly), higher per-node memory overhead, individual operations can be O(n) worst case.

## Which to use

| Use case                         | Recommendation                                                            |
| :------------------------------- | :------------------------------------------------------------------------ |
| General-purpose priority queue   | **BinaryHeap** — best constant factors, cache-friendly                    |
| Frequent merging of heaps        | **SkewHeap** — O(log n) amortized merge vs O(n) for BinaryHeap            |
| Memory-constrained               | **BinaryHeap** — array-backed, no per-node pointer overhead               |
| Streaming top-k / push-pop heavy | **BinaryHeap** — `pushPop` avoids the allocation of a separate push + pop |

**Default choice: BinaryHeap.** Switch to SkewHeap only when merge performance matters.