Heap — max-heap and min-heap properties: Question bank

These items assume the parent note's rules: a heap is a complete binary tree plus a heap-order relation (parent $\geq$ children for max-heap, parent $\leq$ children for min-heap), stored 0-based with $left (i) = 2 i + 1$ , $right (i) = 2 i + 2$ , $parent (i) = ⌊(i - 1) /2 ⌋$ .

True or false — justify

A max-heap is always a sorted array in descending order.

False. The array is only ordered along each root-to-leaf path; e.g. [9,5,8,1,4,7] is a valid max-heap but is not descending (5 then 8). Siblings and cousins are unordered.

Every sorted array (descending) is a valid max-heap.

True. If

A [0] \geq A [1] \geq \dots

, then in particular each parent index sits before and is

\geq

both children, so the heap-order holds. The converse fails, which is why heapsort still needs work.

In a min-heap the largest element must be a leaf.

True. Any non-leaf has a child that is

\geq

it, so a non-leaf can never be the maximum; the max can only sit where it has no children, i.e. a leaf.

In a max-heap the smallest element is always at the last array index.

False. The smallest must be some leaf, but not necessarily the last one. All leaves occupy the back half of the array; the minimum can be any of them.

Two different arrays can represent the same heap-shaped tree of values.

True. Since siblings are unordered, e.g. [9,5,8] and [9,8,5] are both valid max-heaps of the same three values — the heap property does not force a unique layout.

A max-heap lets you find the second-largest element in

O (1)

True. The 2nd largest must be a child of the root (one of at most two nodes), so it is the larger of those two — read directly in

O (1)

because you know exactly where to look, no search needed.

If an array is a valid max-heap, reversing it gives a valid min-heap.

False. Reversing does not respect the parent/child index arithmetic (

2 i + 1, 2 i + 2

), so the order property breaks. Min-heap vs max-heap is a relabelling of the comparison, not of array positions.

A complete binary tree is automatically a heap.

False. Complete is only the shape property. Without the parent-child value relation (heap-order) it is just a balanced tree — e.g. [1,9,2] is complete but violates the max-heap property (parent 1 < child 9).

Every heap is a complete binary tree.

True. Completeness is a required property of a heap by definition, so it can never be optional or missing.

You can perform an

O (lo g n)

search for an arbitrary value in a max-heap just like a BST.

False. Only ancestor–descendant pairs are ordered; siblings are unordered, so you cannot discard half the tree on a comparison. Arbitrary search is

O (n)

Spot the error

"[9, 5, 8, 1, 4, 7] is not a valid max-heap because 5 < 8."

Wrong. Index 1 (value 5) and index 2 (value 8) are siblings, and siblings are never compared. Each is

\leq

their own parent 9, so the heap is valid.

"To insert into a heap, place the new value at the root and sift down."

Wrong. Inserting at the root breaks the shape property and overwrites the extreme element. New values go to the next free leaf (end of array), then sift up.

"In max-heapify at a node, swap the parent with the smaller child so the tree balances."

Wrong. You swap with the larger child. Swapping with the larger guarantees the new parent dominates the other child too; swapping with the smaller could leave a bigger child sitting below a smaller parent.

"For a 0-based array, parent of index

i

⌊ i /2 ⌋

Wrong — that is the 1-based formula. In 0-based it is

⌊(i - 1) /2 ⌋

. Sanity check: parent of index 1 must be 0, and

⌊(1 - 1) /2 ⌋ = 0

, whereas

⌊ 1/2 ⌋ = 0

agrees here but fails at index 2.

"Parent of index 2 (0-based) is

⌊ 2/2 ⌋ = 1

Wrong. Use

⌊(i - 1) /2 ⌋ = ⌊ 1/2 ⌋ = 0

. Index 2 is the right child of the root, so its parent is 0, not 1.

"A max-heap on

n

nodes has height

⌈ lo g_{2} n ⌉

Wrong. The height is

⌊ lo g_{2} n ⌋

. A tree of exactly

n = 2^{h}

nodes has height

h = lo g_{2} n

; adding up to

2^{h + 1} - 1

nodes keeps the same height, so the floor is correct.

"After extracting the root, just delete it and the heap is fixed."

Wrong. Deleting the root leaves a hole and breaks completeness. You move the last leaf into the root, shrink the array, then sift down to restore heap-order.

"Since parents dominate children, the leaf indices are exactly the last

⌈ n /2 ⌉

positions, so we can start heapify at index

n /2

The rule of thumb is right but the boundary is off-by-one. The last internal node is

⌊ n /2 ⌋ - 1

(0-based), so bottom-up build-heap starts there, not at

n /2

Why questions

Why does a heap need both the shape property and the order property, not just one?

Shape alone keeps height

⌊ lo g_{2} n ⌋

(fast, balanced) but says nothing about values; order alone keeps the extreme on top but could be a tall skewed tree with

O (n)

operations. Together you get shallow and extreme-on-top.

Why store a heap in a plain array instead of nodes with pointers?

Because completeness leaves no gaps, so level-order layout is contiguous and child/parent are pure arithmetic (

2 i + 1

, etc.) — no pointer storage, and cache-friendly sequential memory.

Why is peek (reading the extreme)

O (1)

but extract

O (lo g n)

Peek just reads index 0. Extract removes it and must restore heap-order by sifting the replacement down a full root-to-leaf path, whose length is the height

= O (lo g n)

Why can you not use a heap to answer "is value

x

present?" quickly?

A heap orders only ancestors vs descendants; a comparison with a node tells you nothing about which sibling subtree

x

is in, so you cannot prune half the tree — search stays

O (n)

Why does sift-up compare only with the parent, never with siblings?

Because heap-order is defined solely between parent and child. If the new node is

\leq

its parent (min-heap), every ancestor above is already

\leq

that parent, so the whole path is safe — siblings are irrelevant.

Why does inserting at the end of the array preserve completeness?

The next array slot is exactly the next left-to-right position on the last (or a new) level, which is the only place a complete tree is allowed to grow.

Edge cases

Is an empty array (

n = 0

) a valid heap?

Yes, vacuously. There are no parent-child pairs to violate the order property and no shape to break, so both conditions hold trivially.

Is a single-element array [7] a valid max-heap and a valid min-heap?

Yes, both. With one node there are no children, so no comparison ever fails — it satisfies every heap-order rule simultaneously.

Is [5, 5, 5, 5] a valid max-heap and a valid min-heap?

Yes, both. The rules use

\geq

and

\leq

(not strict), so equal parent and child satisfy either direction. Duplicates are always allowed in heaps.

For

n = 1

, what is the height and does

⌊ lo g_{2} n ⌋

still hold?

Height is 0 (just a root, no edges), and

⌊ lo g_{2} 1 ⌋ = ⌊ 0 ⌋ = 0

— the formula holds at the boundary.

When does the right child index

2 i + 2

point past the array, and what does that mean?

When

2 i + 2 \geq n

. It means node

i

has no right child (and if

2 i + 1 \geq n

too, no children at all — it is a leaf), so sift-down must check the bound before comparing.

If a node has only a left child during sift-down, what must you compare against?

Only the left child; there is no right child to consider. Attempting to read index

2 i + 2

would go out of bounds, so the single existing child is the sole swap candidate.

Can the root ever not be the extreme element in a valid heap?

No. By transitivity along every path, the root dominates (max-heap) or is dominated by (min-heap) every node, so it is guaranteed to hold the extreme value.

In a max-heap, can a leaf be larger than an internal node in a different subtree?

Yes. A leaf is only bounded by its own ancestors. A leaf under one branch can exceed an internal node under a different branch — e.g. in [9,5,8,1,4,7] leaf 7 exceeds internal node 5.

Recall

Recall One-line trap summary

Siblings unordered ::: cannot search in $O (lo g n)$ , and "smaller sibling" is never a violation. Insert location ::: next free leaf (array end), then sift up — never at the root. Swap direction in max-heapify ::: with the larger child, so the new parent beats both. 0-based parent ::: $⌊(i - 1) /2 ⌋$ , not $⌊ i /2 ⌋$ (that is 1-based). Last internal node ::: index $⌊ n /2 ⌋ - 1$ (0-based) — where build-heap begins. Height ::: $⌊ lo g_{2} n ⌋$ , and it holds even at $n = 1$ (height 0).

Connections

Parent topic — heap properties
Priority Queue — where insert/extract traps actually bite.
Heapsort — build-heap plus repeated extract; boundary indices matter.
Complete Binary Tree — the shape property behind every edge case.
Binary Search Tree — the contrast that fuels the "search a heap" trap.
Build-Heap (Heapify) O(n) — the last-internal-node boundary.
Big-O Notation — why peek is $O (1)$ and search is $O (n)$ .