Heap data structure and priority queue explained with examples

A heap is a complete binary tree in which every node is ordered against its parent: in a min heap each parent is less than or equal to its children, and in a max heap greater than or equal. Stored in an array, a heap supports insert and extract in O(log n) time and can be built from n items in O(n). A priority queue is the interface a heap usually implements.

What is a heap data structure, and how is it stored in an array?

NIST's Dictionary of Algorithms and Data Structures defines a heap as a complete tree where every node has a key more extreme, greater or less, than or equal to the key of its parent, usually understood to be a binary heap. A complete binary tree has every level full except possibly the deepest, which fills from the left. That shape needs no pointers. The nodes are written into an array level by level.

In the array, the children of each position sit at fixed offsets. NIST and Princeton's Algorithms text, which start counting at 1, put the children of position k at 2k and 2k + 1 and its parent at k/2. Python's heapq module counts from zero, so the children of index k sit at 2k + 1 and 2k + 2, the parent of index i sits at (i - 1) // 2, and the root at index 0 is the smallest item.

The module's rule is that every item is less than or equal to both of its children.

A heap is only partly ordered. Each parent beats its children, so the root is the extreme item, but siblings and cousins carry no order. The list [1, 3, 2, 7, 5, 9] is a valid min heap even though 3 comes before 2.

How do insert and extract work?

Insert adds the new item at the end of the array and swaps it upward while it is smaller than its parent, a step called sift up or swim. Extract removes the root, moves the last item to the root, and swaps it downward with its smaller child until the heap order is restored, called sift down or sink. Both walk one root-to-leaf path, so each costs O(log n). Princeton's text bounds insert at 1 + lg n compares and remove-the-maximum at 2 lg n.

The code builds a min heap by pushing 7, 3, 9, 1, 5 and 2, printing the array after each push.

def push(a, x):
    a.append(x)
    i = len(a) - 1
    while i > 0 and a[(i - 1) // 2] > a[i]:          # sift up
        a[(i - 1) // 2], a[i] = a[i], a[(i - 1) // 2]
        i = (i - 1) // 2

heap = []
for x in [7, 3, 9, 1, 5, 2]:
    push(heap, x)
    print("push", x, "->", heap)

push 7 -> [7]
push 3 -> [3, 7]
push 9 -> [3, 7, 9]
push 1 -> [1, 3, 9, 7]
push 5 -> [1, 3, 9, 7, 5]
push 2 -> [1, 3, 2, 7, 5, 9]

Pushing 1 is the instructive step. It lands at index 3, below 7, so the two swap. It then sits at index 1 below 3, so those swap too, and 1 reaches the root. Pushing 2 lands at index 5 below 9 and swaps once, then stops because the parent 1 is smaller.

Extract works the other way. The next block continues from the heap above.

def pop(a):
    top, last = a[0], a.pop()
    if a:
        a[0] = last
        i = 0
        while True:                                   # sift down
            small = i
            for c in (2 * i + 1, 2 * i + 2):
                if c < len(a) and a[c] < a[small]:
                    small = c
            if small == i:
                break
            a[i], a[small] = a[small], a[i]
            i = small
    return top

print("pop", pop(heap), "->", heap)
print("pop", pop(heap), "->", heap)

pop 1 -> [2, 3, 9, 7, 5]
pop 2 -> [3, 5, 9, 7]

The first pop removes 1, moves the last item 9 to the root and compares it with children 3 and 2. The smaller child, 2, swaps with it, and 9 has no children left to compare. The second pop removes 2, moves 5 to the root, and swaps it with the smaller child, 3.

What is heapify, and why is it O(n)?

Heapify turns an unordered array into a heap in place. It sifts down every parent, starting from the last one and working back to the root. Python's documentation says heapq.heapify transforms a list into a min heap in place in linear time, and Princeton's text states that this sink-based construction is linear.

The linear bound surprises people, because each sift down can cost O(log n). The reason is that most nodes are near the bottom. Princeton's exercise solution shows that at most about n divided by 2^(k+1) nodes have height k and that sinking a node of height k takes at most k exchanges, which sums to a constant times n. The count below confirms it on random data: comparisons stay under 2n.

import random
def sift_down(a, i, n, cnt):
    while True:
        small = i
        for c in (2 * i + 1, 2 * i + 2):
            if c < n:
                cnt[0] += 1
                if a[c] < a[small]:
                    small = c
        if small == i:
            return
        a[i], a[small] = a[small], a[i]
        i = small

def heapify(a):
    cnt = [0]
    for i in range(len(a) // 2 - 1, -1, -1):   # last parent down to the root
        sift_down(a, i, len(a), cnt)
    return cnt[0]

random.seed(7)
for n in (1000, 10000, 100000):
    items = random.sample(range(n), n)         # a random permutation
    print(n, "items:", heapify(items), "compares, 2n =", 2 * n)

1000 items: 1831 compares, 2n = 2000
10000 items: 18675 compares, 2n = 20000
100000 items: 188349 compares, 2n = 200000

C++ documents the same property for std::make_heap, which builds a max heap with at most 3N comparisons. Building by pushing n items one at a time is the slower route, since each push can cost O(log n).

How does heap sort work?

Heap sort builds a heap and then repeatedly extracts the maximum item, and NIST gives its run time as O(n log n) with an in-place implementation. Princeton's text bounds it below 2 n lg n compares and exchanges, and lists heapsort among the sorts that are not stable. The version below uses a min heap from heapq and a copy, so it is not in place, but it shows the idea in five lines.

import heapq

def heap_sort(items):
    heap = list(items)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

print(heap_sort([5, 2, 4, 1, 3]))

[1, 2, 3, 4, 5]

Build costs O(n), and n extractions cost O(log n) each, so the total is O(n log n). For comparison with other sorts, see sorting algorithms explained.

What is the difference between a heap and a priority queue?

A priority queue is an abstract data type, a promised set of operations, and a heap is one data structure that implements it. NIST defines a priority queue as a type that efficiently supports finding the item with the highest priority across a series of operations, with insert, find-minimum or maximum, and delete-minimum or maximum as the basic operations. NIST lists the heap as a structure used inside priority queues.

Other implementations exist, and Princeton's text covers the simple ones. With an unordered array or linked list, either insert or remove-the-maximum takes linear time in the worst case. A binary heap makes both logarithmic, which is why the libraries below build on it.

How do priority queues work in Python, Java and C++?

All three standard libraries ship a heap-backed priority queue, with different defaults. The table compares them using each library's own documentation.

The Python sample uses heapq with tuples of priority and task, the pattern the Python documentation describes for queue.PriorityQueue as (priority_number, data). It also shows heapify, nlargest and the negation trick for a max heap, which works on every Python version.

import heapq

tasks = []
heapq.heappush(tasks, (2, "send invoice"))
heapq.heappush(tasks, (1, "fix login bug"))
heapq.heappush(tasks, (3, "update docs"))
print(heapq.heappop(tasks))          # smallest priority number first
print(tasks[0])                      # peek without removing

nums = [9, 4, 7, 1, 8, 2]
heapq.heapify(nums)                  # in place, linear time
print(nums)
print(heapq.nlargest(3, nums))

maxheap = []
for x in [9, 4, 7, 1, 8, 2]:
    heapq.heappush(maxheap, -x)      # store negatives to get a max heap
print(-heapq.heappop(maxheap))

(1, 'fix login bug')
(2, 'send invoice')
[1, 4, 2, 9, 8, 7]
[9, 8, 7]
9

The C++ sample shows the default max heap and a min heap built with std::greater.

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_heap;                       // largest on top by default
    for (int x : {7, 3, 9, 1, 5, 2}) max_heap.push(x);
    std::cout << "max-heap top: " << max_heap.top() << "\n";

    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    for (int x : {7, 3, 9, 1, 5, 2}) min_heap.push(x);
    std::cout << "min-heap order:";
    while (!min_heap.empty()) {
        std::cout << " " << min_heap.top();
        min_heap.pop();
    }
    std::cout << "\n";
}

max-heap top: 9
min-heap order: 1 2 3 5 7 9

Java's PriorityQueue follows the same idea. The Java SE 21 documentation says its head is the least element, that ties are broken arbitrarily, and that offer, poll, remove() and add run in O(log(n)) time.

What is a heap used for?

Heaps suit any task where the next item to process is the most urgent one. Three uses recur.

Top-k selection keeps a min heap of size k. Each new item that beats the smallest of the k kept items replaces it, so each of the n items costs at most O(log k). Python's heapq.nlargest returns the same result as sorting in descending order and slicing, and the documentation says it performs best for smaller n.

import heapq

def top_k(stream, k):
    heap = []                                   # min heap holding the k largest so far
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)          # pop smallest, push x, one step
    return sorted(heap, reverse=True)

print(top_k([14, 3, 27, 8, 21, 5, 30, 12], 3))

[30, 27, 21]

Shortest paths use a heap too. Princeton's implementation of Dijkstra's algorithm uses an index min priority queue and runs in time proportional to E log V in the worst case on a graph with E edges and V vertices; NIST lists Dijkstra's algorithm as a user of priority queues. Graphs are introduced in Graph Data Structure: Explained with Examples.

Scheduling is the third. The heapq documentation says a heap is a good structure for implementing schedulers, where the smallest scheduled time wins, and its merge function combines several sorted inputs, such as timestamped log files, into one sorted stream.

What are the limits of heaps?

A heap is quick at one question, which item is extreme, and slow at others. Java's documentation lists remove(Object) and contains as linear-time operations, and warns that iterating a PriorityQueue may visit the elements in any order, not sorted order. A heap cannot be searched like a sorted array or a binary search tree, because only parent-to-child order is fixed.

Ties and priority changes need care. Java breaks ties arbitrarily. The Python documentation notes that tuple comparison breaks for equal priorities when the tasks cannot be compared, and suggests storing an entry count between priority and task. It also lists changing a task's priority as a challenge needing extra work. Python's max-heap functions, such as heappush_max, arrived in Python 3.14, so code for older versions should negate values instead.

Where does the heap fit in AI and machine learning study?

Heaps are a practical part of the Python standard library through heapq, and top-k selection is a common data-processing pattern. Certification in Artificial Intelligence and Machine Learning is an online programme from Vishlesan i-Hub, IIT Patna, delivered on Masai's online platform, that covers Python, machine learning, deep learning, generative AI and LLMs, agentic systems and deploying models to production.

Its first module is Core Programming & Analytical Foundations, and later modules include Predictive Modelling & Machine Learning Systems. Details are on the Certification in Artificial Intelligence and Machine Learning page.

Frequently asked questions

What is the difference between a heap and a priority queue?

A priority queue is an abstract data type that returns the highest-priority item first, with insert and delete-min or delete-max operations. A heap is a tree-shaped data structure, usually a binary heap in an array, that implements those operations efficiently. Other structures can also back a priority queue, but the heap is the common choice.

What is the time complexity of heapify?

Heapify runs in O(n) time. Sifting down every parent from the last one to the root costs less in total than n separate O(log n) inserts, because most nodes are near the leaves and sink only a level or two. On random data of 100,000 items, the count was 188,349 comparisons, under 2n.

What is the difference between min heap and max heap?

A min heap keeps the smallest key at the root, with each parent less than or equal to its children. A max heap keeps the largest key at the root. Python's heapq is a min heap and C++'s std::priority_queue is a max heap by default. Either type can be turned into the other by reversing the comparison.

Is a heap the same as a binary search tree?

No. A binary search tree orders every left subtree below its node and every right subtree above it, which supports searching and sorted traversal. A heap orders only parent against children, which gives fast access to the extreme item but no efficient search. A heap is also a complete tree stored in an array.

How do you make a max heap in Python?

Push negated values onto a heapq list and negate them again when popping, which works on every Python version. From Python 3.14 the module also provides heapify_max, heappush_max and heappop_max. In the older approach, store (-priority, task) tuples so the largest priority sorts first.

How does a heap find the top k items in a stream?

Keep a min heap of the k largest items seen so far. For each new item, compare it with the heap's root, which is the smallest kept item, and replace the root if the new item is larger. Each item costs at most O(log k), and the heap never grows beyond k entries.

Next step

Trace the push and pop steps by hand on a new list of six numbers, then check the result against heapq. If Python programming is the next skill to strengthen, see the Certification in Artificial Intelligence and Machine Learning programme from Vishlesan i-Hub, IIT Patna. Readers new to the field can also see what each job title involves in coder vs programmer vs developer vs software engineer, or continue to sliding window and two pointers.