liveBook · Manning

Priority queue

As explained in The Coder Cafe

A priority queue is an abstract data structure in which each element has an associated priority that determines the order of retrieval.

A priority queue retrieves elements according to associated priority rather than arrival order. Binary heaps implement this access pattern efficiently by keeping the minimum or maximum element readily available. section 1.0 section 1.2

Choose the heap variant and operation according to the priority you need:

  • Use a min-heap when retrieval should return the smallest priority value; use a max-heap when it should return the largest. section 1.2
  • Keep the heap as a complete binary tree: levels fill from left to right, while each parent remains smaller or larger than its children. section 1.2
  • Support isEmpty, insert, getMin or getMax, and extractMin or extractMax; insertion and extraction restore the heap through heapify operations. section 1.2
  • Expect O(1) access to the extreme element, O(log n) insertion and extraction, and O(n) construction from an unsorted array. section 1.2 section 1.5

Array-backed heap

For a node at index i, calculate its left child at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2. In the max-heap example, the value 39 at index 1 has children at indices 3 and 4 and its parent at index 0. section 1.2

Inspect the heap and its underlying array representation together to connect the tree property with priority-queue storage. section 1.2

How The Coder Cafe covers it

How deep it goes
Explains heap properties, array indexing, core operations, heapify behavior, and their time complexities.
Examples
Uses a max-heap containing 39 at index 1 to demonstrate child, parent, and array-position calculations.
What you can do after
Operate priority queues through heap operations and select min-heaps or max-heaps for the required retrieval direction.
How it connects
Connects priority queues with binary heaps, binary trees, arrays, min-heaps, max-heaps, and heapify.

Also explained in

Compare how 7 books explain priority queue →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.