binary heap

A binary heap is a binary tree that keeps its elements partially ordered so that the smallest, or largest, value always sits at the root. It combines two rules: the tree is complete, meaning every level is full except possibly the last, which fills from left to right, and it obeys the heap property, which relates each node to its children.

In a min-heap, every parent holds a value less than or equal to both of its children, so the minimum rises to the top. A max-heap reverses the comparison and floats the maximum to the root. Either way, the ordering runs only from parent to child. Siblings have no fixed relationship, which is why a heap is cheaper to maintain than a fully sorted structure.

The complete shape lets a heap live inside a plain array with no pointers. For a node at index i, counting from zero, its children sit at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2 rounded down. Inserting or removing a value temporarily breaks the heap property, so the structure repairs itself by sifting the out-of-place value up or down along a single root-to-leaf path. The following tree pairs each value with its array index:

A min-heap tree with six nodes, each labeled by its value and array index from 0 to 5.
Every Node's Children Sit at Indices 2i+1 and 2i+2

Because that path is never taller than the tree, the core operations stay fast:

  • Peek at the root, the minimum or maximum, in O(1) time.
  • Insert a new value in O(log n) time by sifting it up.
  • Extract the root in O(log n) time by moving the last element into its place and sifting down.
  • Build a heap from an unordered array in O(n) time.

This balance makes the binary heap the standard backing store for a priority queue and the engine behind heapsort. Python’s heapq module implements one as a min-heap over an ordinary list. Other designs, such as binomial and Fibonacci heaps, trade this simplicity for faster merging.

The Python heapq Module: Using Heaps and Priority Queues

Tutorial

The Python heapq Module: Using Heaps and Priority Queues

In this step-by-step tutorial, you'll explore the heap and priority queue data structures. You'll learn what kinds of problems heaps and priority queues are useful for and how you can use the Python heapq module to solve them.

intermediate data-structures python stdlib

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated July 30, 2026
Computer Science Glossary Share Feedback