Heaps and priority queues
Store a complete binary tree in an array, keep the smallest item on top with sift-up and sift-down in O(log n), and use .NET’s PriorityQueue for scheduling, top-k and merging sorted data.
The heap rule
| For the item at index i | Index |
|---|---|
Push: add at the end, sift up
Pop: take the root, sift down
Peek) is O(1).
var heap = new MinHeap();foreach (int x in new[] { 9, 4, 7, 1, 8, 2 }) heap.Push(x); var order = new List<int>();while (heap.Count > 0) order.Add(heap.Pop());Console.WriteLine(string.Join(" ", order)); class MinHeap{ private readonly List<int> _a = new(); public int Count => _a.Count; public int Peek() => _a[0]; public void Push(int x) { _a.Add(x); // add at the end… int i = _a.Count - 1; while (i > 0) { int parent = (i - 1) / 2; if (_a[parent] <= _a[i]) break; // …sift up while smaller than the parent (_a[parent], _a[i]) = (_a[i], _a[parent]); i = parent; } } public int Pop() { int min = _a[0]; _a[0] = _a[^1]; // move the last item to the root… _a.RemoveAt(_a.Count - 1); int i = 0; while (true) // …and sift it down { int l = 2 * i + 1, r = l + 1, smallest = i; if (l < _a.Count && _a[l] < _a[smallest]) smallest = l; if (r < _a.Count && _a[r] < _a[smallest]) smallest = r; if (smallest == i) break; (_a[smallest], _a[i]) = (_a[i], _a[smallest]); i = smallest; } return min; }}1 2 4 7 8 9
PriorityQueue in .NET
PriorityQueue<TElement, TPriority>, a min-heap where each element has a separate priority. The smallest priority comes out first.
var jobs = new PriorityQueue<string, int>();jobs.Enqueue("Check crane certificate", 2);jobs.Enqueue("Fix missing safety rail", 1);jobs.Enqueue("Order extra bolts", 4);jobs.Enqueue("Inspect welds on level 3", 3); Console.WriteLine($"Next: {jobs.Peek()}");while (jobs.TryDequeue(out var job, out int priority)) Console.WriteLine($"{priority}: {job}");Next: Fix missing safety rail 1: Fix missing safety rail 2: Check crane certificate 3: Inspect welds on level 3 4: Order extra bolts
Classic use: the k largest
static List<int> TopK(IEnumerable<int> values, int k){ var heap = new PriorityQueue<int, int>(); // min-heap of the k largest so far foreach (int v in values) { heap.Enqueue(v, v); if (heap.Count > k) heap.Dequeue(); // drop the smallest } var result = new List<int>(); while (heap.Count > 0) result.Add(heap.Dequeue()); result.Reverse(); // largest first return result;} Console.WriteLine(string.Join(" ", TopK(new[] { 5, 12, 3, 41, 7, 19, 8, 26 }, 3)));41 26 19
| Operation | Binary heap | Sorted list | Unsorted list |
|---|---|---|---|
PriorityQueue. For { 1, 4, 9 }, { 2, 3, 10 }, { 5, 6 } the result is 1 2 3 4 5 6 9 10. With N items in total and k arrays, aim for O(N log k).
Show a hint
Show the solution
var parts = new List<int[]> { new[] { 1, 4, 9 }, new[] { 2, 3, 10 }, new[] { 5, 6 } };Console.WriteLine(string.Join(" ", MergeK(parts))); static List<int> MergeK(List<int[]> lists){ var pq = new PriorityQueue<(int list, int index), int>(); for (int i = 0; i < lists.Count; i++) if (lists[i].Length > 0) pq.Enqueue((i, 0), lists[i][0]); var result = new List<int>(); while (pq.TryDequeue(out var pos, out int value)) { result.Add(value); int next = pos.index + 1; if (next < lists[pos.list].Length) pq.Enqueue((pos.list, next), lists[pos.list][next]); // next item from the same array } return result;}1 2 3 4 5 6 9 10
Remember
A min-heap keeps every parent ≤ its children, so the minimum is at the root. A heap is a complete tree stored in an array: parent (i − 1) / 2, children 2i + 1 and 2i + 2. Push sifts up, pop sifts down: O(log n). Peek is O(1); heapify is O(n). PriorityQueue<TElement, TPriority>is .NET’s min-heap; it is not stable. Use a size-k heap for top-k.