Heaps and Priority Queues
3 lessonsAbout 18 minutesIntermediate
This part of the DSA Tutorial runs from Heaps and Priority Queues through to Heap Sort and Streaming Data. There are 3 lessons here, and working through them takes about 18 minutes at a steady pace.
It follows on from Searching, so finish that first if you have not already — the examples below assume you are comfortable with it.
Each lesson below says what it covers before you open it. Read them in order the first time; afterwards this page works as a index you can jump back into when you need to check one thing.
- 1Heaps and Priority QueuesA heap always knows its smallest or largest item in O(1) and inserts in O(log n). Learn how a binary heap is stored in a flat array and how to build one in JavaScript.
- 2Top K ProblemsThe top-k pattern: find the k largest, smallest or most frequent items in O(n log k) with a heap, and know when sorting is the better answer.
- 3Heap Sort and Streaming DataHeap sort gives guaranteed O(n log n) with O(1) extra space. Learn how it works, and how heaps handle streaming problems like a running median that arrays cannot.