Heaps and priority queues

A binary heap is a complete tree stored in an array where parent ≤ children (min-heap) or ≥ (max-heap). std::priority_queue gives O(log n) push/pop extremum—used in Dijkstra, top-K, merge K lists.

Array indexing (0-based)

• Parent of i: (i-1)/2
• Left child: 2i+1, right: 2i+2
• Heapify up/down maintains property

priority_queue demo

#include 
#include 
#include 

int main() {
    std::priority_queue maxHeap;
    maxHeap.push(3); maxHeap.push(7); maxHeap.push(1);
    std::cout << "top=" << maxHeap.top() << "\n";
    maxHeap.pop();
    std::cout << "next=" << maxHeap.top() << "\n";
    return 0;
}

Top-K pattern

Keep size-k min-heap of largest candidates—or max-heap for smallest K—O(n log k).

Important interview questions and answers

1. Q: Min-heap for Dijkstra?
   A: Extract smallest tentative distance—O(log n) per edge relaxation with binary heap.
2. Q: Heap vs sorted array?
   A: Heap O(log n) insert; sorted array O(n) insert but O(1) min if already sorted.

Self-check

1. What is complexity of priority_queue push?
2. How is heap stored in memory?

Tip: priority_queue defaults to max-heap in C++—use greater<> for min-heap.