Heaps

A binary heap is a complete binary tree, stored level by level in an array, in which every parent is no larger than its children. It matters because it is the structure behind every priority queue, from a scheduler choosing its next job to a shortest-path search choosing its next node, and it gives cheap inserts and cheap removal of the smallest item without the cost of keeping everything sorted. The topic starts with the two properties and the index arithmetic that replaces links, then follows a push and a pop swap by swap. It builds a heap from unordered items in linear time and shows why pushing them one at a time is slower. It then implements the heap in three languages beside Python's heapq and Java's PriorityQueue, turns heapq into a largest-first queue, compares a heap with a sorted array, and ends with an exercise on an emergency room's waiting list.