wire / wire-format / binary-heap

Binary heap (priority queue)

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.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Binary heap (priority queue)

wire format

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.

fieldsizemeaning
Array representationarrayComplete binary tree stored in array. Parent of i = floor((i-1)/2). Left child = 2i+1. Right child = 2i+2.
Min-heap propertyinvariantParent ≤ children. Root is the minimum.
Max-heap propertyinvariantParent ≥ children. Root is the maximum.
InsertO(log n)Add to end, sift up (swap with parent if violates heap property).
Extract-minO(log n)Remove root, move last element to root, sift down (swap with smaller child if violates heap property).
HeapifyO(n)Build heap from array: sift down from last internal node to root.
HeapsortO(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)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/binary-heap or /wire-format/binary-heap.json