Chapter 16 — Keeping Your Priorities Straight with Heaps

Heap

A tree-based data structure used to quickly access the highest-priority value

Priority queue

A structure where the highest-priority item is processed first

Max heap

A heap where the greatest value is always at the root

Root of heap

The top node that contains the highest-priority value

Heap condition

Every parent node must be greater than its child nodes in a max heap

Weak ordering

A heap is not fully sorted, but it keeps enough order to find the greatest value quickly

Complete tree

A tree filled from left to right with no gaps except possibly at the end

Why heaps stay balanced

New nodes are inserted at the next available last position

Last node

The final node in the heap’s left-to-right order

Problem of the last node

The challenge of consistently finding where the last node or next open spot is

Heap insertion

Add the new value at the next open last position, then trickle it up

Trickle up

Move a newly inserted value upward by swapping it with its parent until the heap condition is restored

Heap insertion Big O

O(log N), because the value may move up through the heap’s levels

Heap deletion

Remove the root node, replace it with the last node, then trickle the new root down

Trickle down

Move a value downward by swapping it with its larger child until the heap condition is restored

Heap deletion Big O

O(log N), because the new root may move down through the heap’s levels

Reading the highest-priority value

O(1), because it is always at the root

Searching a heap

O(N), because heaps are not designed for finding arbitrary values

Heap vs binary search tree

A BST keeps full searchable order, while a heap only keeps priority order

Heap vs ordered array

Ordered arrays have fast deletion but slow insertion; heaps keep both insertion and deletion fast

Why heaps are good priority queues

They quickly access the highest-priority item and keep insertion/deletion efficient

Array-based heap

A heap stored inside an array instead of linked tree nodes

Root index in array heap

Index 0

Left child formula

left child index = parent index * 2 + 1

Right child formula

right child index = parent index * 2 + 2

Parent formula

parent index = floor((child index - 1) / 2)

Why arrays work well for heaps

Array indexes make it easy to find parents, children, and the last node

Heap pop order

Repeatedly popping a max heap returns values from greatest to smallest

Main lesson of Chapter 16

Heaps are optimized for priority queues because they keep the highest-priority value accessible while supporting fast insertion and deleti