wire / wire-format / binary-heap
A binary heap is a complete binary tree stored in an array. Min-heap: parent ≤ children. Max-heap: parent ≥ children. Operations: insert (O(log n)), extract-min/max (O(log n)), peek (O(1)), heapify (O(n)). Used for priority queues, heapsort, and Dijkstra's algorithm.
aka: Binary heap (priority queue)
spec: Binary heap
A binary heap is a complete binary tree stored in an array. Min-heap: parent ≤ children. Max-heap: parent ≥ children. Operations: insert (O(log n)), extract-min/max (O(log n)), peek (O(1)), heapify (O(n)). Used for priority queues, heapsort, and Dijkstra's algorithm.
| field | size | meaning |
|---|---|---|
| Array representation | array | Complete binary tree stored in array. Parent of i = floor((i-1)/2). Left child = 2i+1. Right child = 2i+2. |
| Min-heap property | invariant | Parent ≤ children. Root is the minimum. |
| Max-heap property | invariant | Parent ≥ children. Root is the maximum. |
| Insert | O(log n) | Add to end, sift up (swap with parent if violates heap property). |
| Extract-min | O(log n) | Remove root, move last element to root, sift down (swap with smaller child if violates heap property). |
| Heapify | O(n) | Build heap from array: sift down from last internal node to root. |
| Heapsort | O(n log n) | Build max-heap, then repeatedly extract max (swap root with last, sift down). In-place, not stable. |
example:
00 00 00 00
Binary heap (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/binary-heap
or /wire-format/binary-heap.json