What is a heap data structure, and how does PriorityQueue<TElement,TPriority> work in .NET? Show how you would find the top K items from a large stream efficiently.

1. Sift up and sift down

Insert 1 into [2,5,3,9,6,8,4]:
  append → [2,5,3,9,6,8,4,1]   1 at index 7, parent index 3 (9) → swap
         → [2,5,3,1,6,8,4,9]   parent index 1 (5) → swap
         → [2,1,3,5,6,8,4,9]   parent index 0 (2) → swap
         → [1,2,3,5,6,8,4,9]   done (at most log n swaps)

Remove min from [2,5,3,9,6,8,4]:
  take 2 from the root; move the last item (4) to the root → [4,5,3,9,6,8]
  sift down: children are 5 and 3, smaller is 3 → swap → [3,5,4,9,6,8]
  4 is now at index 2; its only child is 8 → 4 ≤ 8, done

2. Why .NET uses a 4-ary heap

Each node has four children, so the tree is shallower (log₄ n) and children sit next to each other in memory. Sift-down compares more children per level but touches fewer levels and cache lines; in practice it is faster for typical workloads.

3. Top-K patterns

Compare: full sort is O(n log n) time and O(n) memory, which loses badly when K is small and n is large or unbounded.

4. Handling priority updates

Without decrease-key, use lazy deletion: enqueue the item again with the new priority and keep a dictionary of current priorities; when you dequeue an entry whose priority is stale, skip it. This is the standard way to write Dijkstra with PriorityQueue.

5. Heapsort

Build a heap in O(n), then repeatedly remove the max: O(n log n) time, O(1) extra space, not stable. .NET's Array.Sort uses introsort, which falls back to heapsort when quicksort recursion gets too deep.

6. Try it yourself

1. Implement top-K with PriorityQueue and compare with OrderByDescending().Take(K) on 10 million random ints using BenchmarkDotNet (time and allocations).
2. Merge 5 sorted arrays into one sorted output using a heap of (arrayIndex, position).
3. Implement a running median with two heaps.

// Top K largest items from a large or unbounded stream: O(n log K) time, O(K) memory
public static List<RequestLog> SlowestK(IEnumerable<RequestLog> logs, int k)
{
    var heap = new PriorityQueue<RequestLog, TimeSpan>(k);   // min-heap by duration
    foreach (var log in logs)
    {
        if (heap.Count < k)
        {
            heap.Enqueue(log, log.Duration);
        }
        else if (heap.TryPeek(out _, out var smallest) && log.Duration > smallest)
        {
            heap.EnqueueDequeue(log, log.Duration);           // push then pop the smallest, one sift
        }
    }

    var result = new List<RequestLog>(heap.Count);
    while (heap.TryDequeue(out var item, out _)) result.Add(item);
    result.Reverse();                                          // slowest first
    return result;
}

// Max-heap via a reversed comparer
var maxHeap = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
maxHeap.Enqueue("low", 1);
maxHeap.Enqueue("high", 10);
Console.WriteLine(maxHeap.Dequeue()); // high

// Merge K sorted sequences
public static IEnumerable<int> MergeSorted(IReadOnlyList<IEnumerator<int>> sources)
{
    var heap = new PriorityQueue<int, int>();   // element = source index, priority = current value
    for (int i = 0; i < sources.Count; i++)
        if (sources[i].MoveNext()) heap.Enqueue(i, sources[i].Current);

    while (heap.TryDequeue(out var i, out var value))
    {
        yield return value;
        if (sources[i].MoveNext()) heap.Enqueue(i, sources[i].Current);
    }
}