Heap
heap
Data Structures
Heaps & Priority Queue
Pull the next task in priority order from a stream of millions, and a sorted array gives you `O(1)` extract but `O(n)` insert; a sorted linked list flips the costs but stays linear; a balanced BST hits `O(log n)` for both but with substantial pointer overhead. A **Heap** quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root. This lesson covers the heap property, the parent-and-child index formulas (`parent = (i-1)/2`, `left = 2i+1`, `right = 2i+2`) that let array indices encode tree structure with no pointers, sift-up and sift-down for `O(log n)` insert and extract, and the linear-time `heapify` build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim. In **Trees: Binary Tree Fundamentals**, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. **Arrays & Strings** is what makes the implicit storage cheap: a flat array gives `O(1)` parent and child access through arithmetic, with no allocations per node. Next, **Binary Search Tree (BST)** trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.
Not Started
0%
Practice Problems
Kth Largest Element in a Stream
Design a class that finds the kth largest element in a stream of numbers using a min-heap.
Last Stone Weight
Simulate smashing the two heaviest stones together repeatedly using a max-heap and return the weight of the last remaining stone.
Find Median from Data Stream
Design a data structure that efficiently finds the median from a stream of integers using two heaps.
Merge k Sorted Lists
Merge k sorted linked lists into one sorted linked list using a divide-and-conquer or min-heap approach.
Minimum Interval to Include Each Query
Given a list of intervals and a list of queries, for each query find the size of the smallest interval that contains it, or -1 if no interval contains it.
Swim in Rising Water
Given an n x n grid of elevations, find the minimum time t at which you can swim from the top-left to the bottom-right corner.
Design Twitter
Design a simplified Twitter with post, follow/unfollow, and a news feed that merges recent tweets from followed users using a heap.
IPO
Maximize capital after completing at most k projects by greedily selecting the most profitable affordable projects using a max-heap.
K Closest Points to Origin
Find the k closest points to the origin using a max-heap to efficiently track the k smallest distances.
Find K Pairs with Smallest Sums
Given two sorted arrays, find the k pairs with the smallest sums using a min-heap to efficiently explore candidates.
Kth Largest Element in an Array
Find the kth largest element in an unsorted array using a min-heap or quickselect algorithm.
Meeting Rooms II
Given an array of meeting time intervals, determine the minimum number of conference rooms required to hold all meetings.
Network Delay Time
Given a network of n nodes and weighted directed edges representing signal travel times, find the time it takes for a signal sent from node k to reach all nodes.
Task Scheduler
Determine the minimum number of intervals needed to execute all tasks given a cooldown period between identical tasks.
Code Snippets
Min-Heap Template
JavaScript still has no built-in priority queue, so most real-world code rolls its own min-heap. This snippet covers a generic comparator-based heap with push and pop, the sift-up and sift-down internals that make both O(log n), and a heapify-from-array helper that builds a heap from an arbitrary input in O(n).
Dijkstra Shortest Path Template
Dijkstra's algorithm finds the shortest path from a source to every reachable node in a weighted graph with non-negative edge weights. The textbook O((V + E) log V) implementation pairs a min-heap with a relaxation loop. This snippet covers the heap-based template, a parent-tracking variant that reconstructs the actual path, and an early-exit form for single-target queries.
heapq Min-Heap Recipes
Python's `heapq` module turns any list into a binary min-heap in place, supporting O(log n) push and pop. It is the priority-queue primitive that powers Dijkstra, Top-K, and merging sorted streams. This snippet covers the basic push and pop, the Top-K largest pattern using `nsmallest` and `nlargest`, and the merge of multiple sorted iterables in O(N log K).
Min-Heap via std::priority_queue
`std::priority_queue` is a max-heap by default. To get a min-heap you flip the comparator. This snippet shows the three common forms: a min-heap of ints with `std::greater`, a min-heap of pairs sorting by first element, and a custom comparator over a struct for things like Dijkstra. All run in O(log n) per push/pop.
Community
Furthest Building You Can Reach
Use bricks for short climbs and ladders for tall ones, swapping greedily to maximize reach.
Top K Frequent Words
Return the k most frequent words, breaking frequency ties alphabetically and returning results in descending frequency.
Reorganize String
Rearrange a string so no two adjacent characters are equal, or report that no rearrangement exists.
Top K Frequent Elements
Return the k most frequent elements in O(n) time using bucket sort by frequency. A staple of mid-level interview rotations.
Heaps and Priority Queues: When the Order Matters
Why a binary heap is the right shape for top-K, Dijkstra, k-way merge, and scheduling, plus the one trap I have hit twice with mutable heap entries.
Path with Maximum Probability
Find the path between two nodes that maximizes the product of edge success probabilities, via modified Dijkstra.
Minimum Number of Refueling Stops
Reach the target with the fewest refueling stops, deferring fuel choices via a max-heap of passed stations.