Course contentsShow
← Computer Science
Lesson 610 of 2,87214. Heaps and Priority QueuesFree lesson

Heap as Priority Queue Implementation

Explain how binary heaps efficiently implement priority queues with O(log n) insert and extract operations.

Heap as Priority Queue Implementation

You'll learn why binary heaps are the go-to data structure for implementing efficient priority queues.

The Perfect Match

A priority queue is an abstract data type where elements have priorities, and you always want quick access to the highest (or lowest) priority item. Think of an emergency room: patients aren't served first-come-first-served, but by urgency.

Binary heaps are ideal for this because they naturally maintain the heap order property—the most important element is always at the root, instantly accessible.

Why Heaps Excel Here

The priority queue ADT requires two critical operations:

  • Insert a new element with a priority
  • Extract the highest/lowest priority element

Binary heaps deliver both in O(log n) time:

  1. Insert uses upward bubbling to restore heap order after adding to the end
  2. Extract-Max/Min removes the root and uses downward bubbling to fix the structure

Compare this to alternatives:

  • Unsorted array: Insert is O(1), but extract requires scanning all elements—O(n)
  • Sorted array: Extract is O(1), but insert requires finding position and shifting—O(n)
  • Heap: Both operations are O(log n)—balanced and efficient

The Implementation Link

You've already learned all the mechanics: array representation, parent-child formulas, bubbling operations, and extract. A priority queue simply uses these heap operations as its internal implementation, often wrapping them with names like enqueue() (insert) and dequeue() (extract).

Key Takeaway: Binary heaps implement priority queues optimally with O(log n) insert and extract operations, making them the standard choice when you need efficient access to the most important element in a dynamic collection.