Learn / DSA
Module 09 · DSA · Four patterns the ladders lean on
Continue where you left off ×
Before you start. Trees (BST, balancing, heaps, tries) told you how a heap works: a pile where every parent is smaller than its children, so the smallest value always sits on top. Clinic #19: Kth Largest Element in an Array and Clinic #20: Top K Frequent Elements used one to keep the biggest few of a list. This lesson takes the same pile and shows the three jobs it gets hired for most often, one of which needs two piles at once.
The idea in 30 seconds
A heap is a pile that always shows its extreme on top. A min-heap shows the smallest, a max-heap shows the biggest.
Python’s heapq is a min-heap only, so a max-heap stores negated values.
Top-k keeps the biggest k of many using a min-heap of size k, because a new value only has to beat the weakest seat.Two heaps give a running median: lower half in a max-heap, upper half in a min-heap, sizes never more than one apart, the median at the seam.A k-way merge weaves k sorted lists using a min-heap of size k, and the list index in each entry breaks ties.
If you need everything in order and nothing is changing, a heap is the wrong tool. Sort.
Read the story
Lesson 70 of 74 in DSA
The rest of this lesson is part of a plan.
A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year , or $19.50 for your first yearLAUNCH50 , ends 1 Nov, 18:30 UTC .
See plans Already a member? Sign in
Or start free : a free account opens lessons 2 and 3 of every track.
In this lesson 1964: two pages in the June issue, and a pile that always knows its weakest member Job one: top-k, a scoreboard with k seats and the weakest score on top Job two: the running median, two scoreboards facing each other Job three: k-way merge, k sorted heats and a board with k seats When the pile is the wrong tool Terms it explains: min-heap, Top-k, median, max-heap, Two heaps, k-way merge, heap.
Review DSA
Mark as read Saved in this browser, and to your account when you sign in.