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.


In programming, "the heap" is a term referring to an area of memory from which storage for non-local variables can be dynamically allocated. For such questions, use the tag instead.

history | excerpt history