Binary Heaps

MIT 6.006 Introduction to Algorithms, lecture 8, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces the priority queue, a way to store items and always pull out the most important one, and shows why sorting with it is useful.

Key ideas

A priority queue stores items that each have a key, which acts as a priority. Its main job is to find the item with the maximum key and remove it. 0:57
The two main operations are insert, which adds an item with its key, and delete max, which removes and returns the largest item. Finding the max alone can be done by deleting it and putting it back, but it can often be done faster. 2:03
A binary heap is a simpler structure than a set AVL tree. It gets about the same time bounds, builds a little faster, and allows sorting in place. 4:37
A plain unsorted array makes insert fast but delete max slow. A plain sorted array makes delete max fast but insert slow. The goal is a structure that is good at both. 5:47
Any priority queue can be used to sort. Insert every item, then repeatedly delete the max. Since the largest comes out first, you get the items in reverse order, and reversing them gives sorted order. 8:29

Words to know

priority queue: A collection of items where each item has a priority, and you can always take out the item with the highest priority next.
amortized: Averaged over many operations. A single step may be slow, such as resizing an array, but the average cost per step stays low.
in-place: Done using the same memory you already have, without making a big new copy of the data.
augmentation: Extra information added to each node of a tree so that a certain question, like finding the max, can be answered faster.

Example

Think of a hospital emergency room. Patients arrive at different times, but the doctor always treats the most urgent patient next, not the one who arrived first. A priority queue works the same way: items come in whenever they like, and you always take out the one with the highest priority.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains how a binary heap stores items in a plain array while keeping the shape of a balanced tree, which lets it sort quickly without extra memory.

Key ideas

Each sorting method is a different data structure plugged into the same recipe: insert everything, then keep pulling out the biggest item. Using a balanced tree gives AVL sort, which is fast. Using plain arrays gives selection sort and insertion sort, which are slow. 10:18
An unsorted array gives selection sort, and a sorted array gives insertion sort. The lesson says these are old friends from earlier lectures seen in a new way. 11:04
The goal is a sort that is both fast and in place. In place means it uses almost no extra memory beyond the items themselves. Heaps are designed to hit that goal. 13:21
A heap stores its items in an array, but the array is laid out as a tree. The tree is a complete binary tree, which is always balanced, so no rotations are needed to keep it balanced. 15:06
The array is filled in depth order: the top level first, then the next level, always left to right. A complete binary tree has one matching array, and each array has one matching tree. 17:29

Words to know

complete binary tree: A tree where every level is full, except possibly the last. The last level is filled from the left with no gaps.
in place: Using only the memory that already holds the items, plus a few extra pointers or counters. No large second copy is made.
depth: How many steps a node is below the top of the tree. The top node is at depth 0.
bijection: A perfect matching where each item in one group pairs with exactly one item in the other group, with no leftovers on either side.

Example

Think of filling a theater row by row, from the front row to the back, and filling each row from left to right. Once you know how many people are coming, there is only one way to seat them. The seating chart can be written as a simple list, so you never need to draw the rows.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how a binary heap can be stored as a plain array, using index math instead of pointers, and what the max-heap rule guarantees about where the biggest item sits.

Key ideas

A binary heap is stored as a plain array with no pointers. Because the tree is complete, you can find any node's children and parent with simple arithmetic on its index. 20:28
For a node at index i, the left child is at 2i + 1 and the right child is at 2i + 2. To go from a child back to its parent, you subtract 1 and then divide by 2, dropping any remainder. 22:39
The max-heap property says each node is greater than or equal to both of its children. It only compares a node with its own children, not with the whole subtree. 26:41
If the max-heap property holds everywhere, every node is greater than or equal to all the nodes below it. So the biggest item is always at the top, which is why heaps suit priority queues. 27:34

Words to know

implicit data structure: A way of organizing data where the structure comes from the position of each item in an array, so no extra links or pointers need to be stored.
complete binary tree: A tree where every level is full, except possibly the last, which is filled from left to right. Each node has at most two children.
max-heap property: The rule that every node must be greater than or equal to its children. It is a local rule about a node and its two children.
integer division: Dividing two whole numbers and throwing away the remainder, so 7 divided by 2 gives 3.

Example

Think of a row of numbered mailboxes, with box 0 at the top and boxes 1 and 2 below it, then 3 to 6 below those, and so on. If you know you are at box 1, you can work out that its two helpers are boxes 3 and 4 without any labels or signs pointing to them. The numbers themselves tell you the family links.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how a binary heap adds and removes its biggest item by working only at the end of an array and then moving one item up or down the tree.

Key ideas

The easy place to remove an item is the last leaf, which is the last spot in the array. Removing it keeps the tree complete, so the tree still has no gaps. 30:18
To insert a new item, put it in the last leaf position, which is the end of the array. This is the only spot an array can add to easily. 31:09
The new item may be bigger than its parent, which breaks the max-heap rule. If so, swap it with its parent and keep going up, one level at a time, until the rule holds again. 33:49
To delete the biggest item, swap it with the last leaf and remove the last leaf. The small value now at the root must then be pushed down the tree until the rule holds again. 37:35

Words to know

leaf: A node at the bottom of a tree that has no children below it.
complete binary tree: A tree where every level is full, except possibly the last, and the last level fills up from left to right with no gaps.
max-heap property: The rule that every parent is greater than or equal to its children, so the biggest item is always at the top.
recursive: A way of writing a process that repeats itself on a smaller piece each time, like moving up or down one level at a time.

Example

Think of a sports team ranked from best to worst, where each player must rank above anyone they coach. A new player joins at the bottom of the list, and if they are better than the player above, they swap places and keep moving up until the ranking is correct again. The same idea works in a heap, with one item moving up or down at a time.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:42

This part shows how a max-heap fixes itself after its top item is removed, how heapsort sorts an array in place using that same method, and why building a heap from scratch can be done in linear time.

Key ideas

When the wrong item sits near the top, it moves down by swapping with its larger child. The larger child is chosen so that the parent-child edge still satisfies the max-heap property. 40:18
The item keeps sinking, one level at a time, until it reaches a leaf or no longer has a child bigger than itself. Then the whole heap is valid again. 42:06
Because the item moves down one level per step, the work takes time proportional to the tree's height, which is about log n. 43:36
Heapsort works in place. It treats the start of the array as a priority queue that grows one item at a time, and each removed maximum goes to the end, so the array ends up sorted. 47:34
A heap can be built in linear time by adding all items first and then fixing them from the bottom up. Most nodes are near the leaves, so most fixes are short. 49:17

Words to know

max-heap property: The rule that every parent must be greater than or equal to each of its children.
in-place: Done inside the array you already have, without needing extra space for a new array.
prefix: The first part of an array, from the start up to some position.
heapsort: A sorting method that builds a max-heap, then repeatedly removes the largest item and places it at the end of the array.

Example

Imagine a company org chart where every boss must earn more than each person who reports to them. If a new hire is too senior for a junior spot, they swap down with the stronger of their two direct reports, and keep swapping until they settle into a spot that fits.

3 checked practice questions for this part are in the app.

← Lecture 7: Binary Trees, Part 2: AVL · Lecture 9: Breadth-First Search →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York