Heap (Priority Queue)

Question 1

Where is the maximum element always located in a Max Heap?

Accepted Answer

At the root (index 0) — The max heap property ensures that the root is always the largest element.

Question 2

A binary heap is structurally a…

Accepted Answer

A complete tree satisfying the heap property — A heap is a complete binary tree (every level full except possibly the last, filled left-to-right) where each parent dominates its children (min- or max-heap).

Question 3

In a MIN-heap, the heap property states that each node is…

Accepted Answer

Less than or equal to children — Every parent ≤ its children, so the global minimum sits at the root. A max-heap reverses this (parent ≥ children).

Question 4

What are the complexities of insert and extract-min in a binary heap?

Accepted Answer

O(log n) insert / O(log n) extract — Insert sifts up and extract-min sifts down along a root-to-leaf path of length O(log n). Peek (read root) is O(1).

Question 5

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

Accepted Answer

It's a complete tree, indexed 2i+1/2i+2 — Completeness means there are no gaps, so the tree maps onto contiguous array indices with simple parent/child arithmetic.

Question 6

Building a heap from an unsorted array of n elements (bottom-up) costs…

Accepted Answer

O(n) — Bottom-up heapify is O(n): nodes near leaves sift down little; summing the work gives a bound of O(n), better than n inserts (O(n log n)).

Question 7

What does PEEK (find-min/max) cost in a heap?

Accepted Answer

O(1) — root is always at top — The extreme element is always at the root (array index 0), readable in O(1). Removing it costs O(log n).

Question 8

A primary application of a (min-)heap is…

Accepted Answer

A priority queue for Dijkstra — Heaps implement priority queues, repeatedly serving the highest-priority (min/max) element in O(log n) — central to greedy graph algorithms and schedulers.

Question 9

Is a binary heap fully sorted?

Accepted Answer

No, only a partial order — A heap guarantees the root is the extreme, but siblings and cousins are unordered. To get a sorted sequence you repeatedly extract (heapsort).

Question 10

After inserting a new element at the next array slot, the heap property is restored by…

Accepted Answer

Sift-UP — A new element is appended as the last leaf and swapped upward with its parent until the heap property holds — O(log n).

Heap (Max-Heap)

Max-Heap Structure

What does it cost?

Test your knowledge

Where is the maximum element always located in a Max Heap?

The short version

In more depth

The Priority Struct

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?