A heap is a tree-based data structure that satisfies the heap property. For questions about memory allocated from the system heap, use the [memory-management] tag.
A heap is a specialized tree-based data structure that is either
- a max heap: the largest key is in the root node, and the keys of parent nodes ≥ those of the children
- a min heap: the smallest key is in the root node, and the keys of parent nodes ≤ those of the children
A min heap is a particularly efficient data structure for implementing priority queues, where it is necessary to repeatedly remove the element with the smallest key. Each
find_min() operation takes constant time, and each
delete_min() operation can be accomplished in Θ(log n) time.