---
title: "Heaps and Priority Queues"
description: "A binary heap keeps the smallest item at the root using an array and a simple shape rule, so insert and extract both cost log n. It gives a sort that meets the comparison bound and, more usefully, a q"
canonical: https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs
source: https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Heaps and Priority Queues

A binary heap keeps the smallest item at the root using an array and a simple shape rule, so insert and extract both cost log n. It gives a sort that meets the comparison bound and, more usefully, a queue ordered by importance rather than by arrival.

Subject: Computing · Area: Algorithms & Data Structures · Ages 19 to 20
Page: https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs

## Ready when they can

- Insert into a heap and restore the heap property by sifting up
- Extract the minimum and restore the property by sifting down
- Say why a heap is stored in an array with no pointers at all

## Lesson: Heaps that always hand you the smallest first

A priority queue hands you the most important item first, not the oldest one. You can build one from a sorted list, where inserts shift things and removal is instant, or from a binary heap, which keeps both operations cheap.

A heap needs no pointers because its shape is fixed: every level is full except possibly the last, which fills left to right. So the tree lives in a plain array with the root at index 0 and the children of index i at 2i+1 and 2i+2.

**Example.** A value rule keeps the smallest item at the root: every parent is no larger than its children. Insert appends the new item at the end and sifts up, swapping with its parent until the rule holds. Extract removes the root, moves the last item to the root, then sifts down, swapping with the smaller child until the rule holds.

**Tip.** Each fix walks one root to leaf path, so insert and extract each cost log n. Extracting the minimum again and again sorts in n log n, which meets the comparison bound, and schedulers use the same step to answer what is most urgent right now.

**Recap.** A heap stores a fixed shape tree in an array and sifts along one path, so the smallest item is always ready in log n time.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Queues: First In, First Out](https://lightmysky.com/learn/computing/queues-first-in-first-out-mt_4U1bT0JW4g)
- [The Comparison-Sorting Lower Bound](https://lightmysky.com/learn/computing/the-comparison-sorting-lower-bound-mt_7AfUsPV-jW)
- [Trees and Binary Search Trees](https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b)

## Opens up

- [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr)