# Heap / Priority Queue
Confidence: high
Last verified: 2026-05-22
Generation: human_only


## TL;DR

A heap is a complete binary tree with the heap property (parent ≤ children for min-heap). O(1) peek, O(log n) insert/extract. Array-based representation: children of i are 2i+1, 2i+2.

## Core Explanation

Binary heap is the most common implementation. Heapify (construction): O(n) bottom-up. Heapsort: build heap + n extractions = O(n log n) in-place. Priority queues in Dijkstra, job scheduling, event simulation. Fibonacci heap achieves O(1) insert, amortized O(log n) extract.

## Further Reading

- [Introduction to Algorithms (CLRS)](undefined)