Heaps and priority queues, tries — Data Structures & Algorithms

6. Heaps and priority queues, tries

IntermediateMediumLesson 6 of 10

A binary heap is a complete binary tree stored in an array where every parent ≤ its children (min-heap). The smallest item is always at index 0.

Operation	Cost
Peek min	O(1)
Insert (bubble up)	O(log n)
Remove min (move last to top, sift down)	O(log n)
Build from n items	O(n)

Array layout: children of index i are at 2i+1 and 2i+2, parent at (i−1)/2 — no pointers needed.

csharp

// Top-K largest numbers in O(n log k) with a min-heap of size k
int[] TopK(int[] nums, int k)
{
    var heap = new PriorityQueue<int, int>();
    foreach (var n in nums)
    {
        heap.Enqueue(n, n);
        if (heap.Count > k) heap.Dequeue();   // drop the smallest
    }
    return heap.UnorderedItems.Select(x => x.Element).ToArray();
}

A trie (prefix tree) stores strings character by character; finding all words with a prefix costs O(length of prefix) — autocomplete and routing tables.

csharp

public class Trie
{
    private sealed class Node { public Dictionary<char, Node> Next = []; public bool End; }
    private readonly Node _root = new();
    public void Insert(string word)
    {
        var node = _root;
        foreach (var c in word)
        {
            if (!node.Next.TryGetValue(c, out var child)) node.Next[c] = child = new Node();
            node = child;
        }
        node.End = true;
    }
    public bool StartsWith(string prefix)
    {
        var node = _root;
        foreach (var c in prefix)
        {
            if (!node.Next.TryGetValue(c, out var child)) return false;
            node = child;
        }
        return true;
    }
}