Heaps and Tries

An emergency room's most-urgent-first waiting list, built as a heap and used as your language's priority queue; then the trie, which lets a phone suggest the next word.

Updated

Heaps

  1. Who's Next in the Emergency Room? Heaps (Journeyman): Always call the most urgent patient next while new ones keep arriving, even on a day of 10,000: why an unsorted list and a sorted list both slow down, and the structure that fixes them, the heap, which keeps a tree in a plain array.
  2. Fair Ties, Ready-Made: Priority Queues in Your Language (Journeyman): See the most urgent patient first and, of two equally urgent, the one who has waited longer, with the priority queue your language already has (PriorityQueue in C# and Java, heapq in Python) or a small one in JavaScript and TypeScript, which have none.

Tries

  1. How a Phone Suggests the Next Word: Tries (Journeyman): Suggest words from a 100,000-word dictionary on every keypress, and learn new words as they're typed: why checking every word, a hash set and a sorted array each fall short, and the structure that fixes them, the trie.

Exercise: Emergency Room Triage

  1. Exercise: Emergency Room Triage (Journeyman): Build an emergency room's waiting list: most urgent first, fair ties, arrivals and calls all night, and a 100,000-patient disaster drill in under 3 seconds; then see what the same structure does for Module 7's maps and routes.