⛰️ Binary Heap — Priority Queue

Why can a binary heap be stored in an array without pointers?

Because it is a complete binary tree, filled level by level with no gaps, a node's parent and children can be computed directly from its array index (parent = ⌊(i−1)/2⌋, children = 2i+1 and 2i+2). This avoids the memory overhead of pointer-based tree nodes and gives excellent cache locality compared with linked structures.

What is the time complexity difference between sift-up and sift-down?

Both run in O(log n) in the worst case, since each follows only a single root-to-leaf path of length ⌊log₂ n⌋. Sift-up makes at most one comparison per level against the parent, while sift-down makes up to two comparisons per level against both children, so sift-down has a slightly larger constant factor despite sharing the same asymptotic bound.

Why is building a heap from n elements O(n) rather than O(n log n)?

Floyd's build-heap algorithm calls sift-down only on internal nodes, starting from the last one and working up to the root. Most nodes are near the bottom of the tree, where a sift-down can travel only a short distance; summing the work across all levels gives a geometric series that converges to O(n), unlike the O(n log n) cost of inserting n elements one at a time.

What is the difference between a min-heap and a max-heap, and how does a heap compare to a balanced BST for a priority queue?

A min-heap keeps the smallest value at the root (parent ≤ children); a max-heap keeps the largest (parent ≥ children) — the same algorithms apply with the comparison flipped. Compared with a balanced binary search tree, a heap gives the same O(log n) insert and O(log n) extract-min, but with a simpler array-based implementation, no rebalancing logic, and O(1) peek at the minimum, whereas a BST offers ordered traversal and O(log n) search for arbitrary keys that a heap does not support.