Implement Max Heap

Implement a max-heap — a priority queue that always keeps the largest element reachable in O(1) — supporting:

insert(x) — add x to the heap.
getMax() — return the current maximum (called only when non-empty).
extractMax() — remove and return the current maximum (called only when non-empty).
size() — return the number of elements.

insert and extractMax should run in O(log n). Store the heap in an array using the standard index arithmetic: the children of i are 2i+1 and 2i+2, the parent is (i-1)/2.

Hints

· Stuck? Reveal one nudge at a time.

Store the heap in an array; the maximum lives at index 0.

insert: append at the end and swap upward while larger than the parent.

extractMax: move the last element to the root, then sift it down past its larger child.

Common doubts

Only the comparisons flip: sift up while LARGER than the parent, and sift down toward the LARGER child. The structure and complexity are identical.

It keeps the tree complete (no gaps), and a single sift-down then restores the heap property.

Swapping the larger child up guarantees it ends ≥ its new sibling, preserving the max-heap property.

Interview follow-ups

· What an interviewer asks next.

Negate values on insert and negate again on getMax/extractMax, or flip the comparisons.

Bottom-up heapify in O(n) instead of O(n log n).

Fun facts

C++'s std::priority_queue is a max-heap by default — exactly this structure.
Max-heaps power heap sort's ascending order: repeatedly extract the max to the back.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: insert(3), insert(8), insert(5), getMax(), extractMax(), getMax()
Output: null null null 8 8 5
The maximum is 8; after extracting it, the new maximum is 5.

Example 2

Input: insert(2), size(), getMax()
Output: null 1 2
One element: size is 1 and the max is 2.

Constraints

- -10^9 <= x <= 10^9 - At most 2 * 10^4 operations - getMax / extractMax only on a non-empty heap

A max-heap keeps the largest element at the root (index 0) of a complete binary tree stored in an array. The brute-force unsorted list makes insert trivial but pays O(n) to find the maximum on every getMax/extractMax. The real heap keeps the array partially ordered so the maximum is always at index 0, repaired in O(log n):

insert(x) — append x, then sift up: while it's larger than its parent, swap them.
extractMax() — the answer is arr[0]. Move the last element to the root, drop the last slot, then sift down: while the node is smaller than its larger child, swap them.

getMax is just arr[0]; size is the length. Each repair walks one root-to-leaf path — O(log n). (It's the exact mirror of a min-heap: flip every comparison.)

Prerequisites

Before you start

· Concepts used directly in the solution.

Array-as-tree. parent (i-1)/2, children 2i+1 and 2i+2.

Sift up / sift down. the two O(log n) repairs, comparing toward the larger side.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Are getMax/extractMax ever called on an empty heap?”

No — assume non-empty for those.

“Which child do I compare against in extractMax?”

The larger child, so the swapped-up value stays ≥ its sibling.

The ideal opening — say it like this

Array with the max at index 0: insert appends and sifts up, extract-max moves the last element to the root and sifts down toward the larger child.

Both repairs are one root-to-leaf path — O(log n) — and getMax is O(1).

Understand the problem

Worked example — insert 3, insert 8, insert 5, getMax, extractMax, getMax

insert 3 -> [3]
insert 8 -> [3,8] sift up -> [8,3]
insert 5 -> [8,3,5]
getMax   -> 8
extractMax -> 8; move 5 up -> [5,3] sift down -> [5,3]; returns 8
getMax   -> 5

Key observations

1Aha

The max is always at index 0

The heap property forces the global maximum to the root.

2Aha

Insert sifts up, extract sifts down

Each disturbs a single path and is repaired in O(log n).

3Aha

It's the min-heap with flipped comparisons

Everywhere a min-heap uses <, a max-heap uses >.

Brute force vs optimal

	Unsorted list	Array binary heap
insert	O(1)	O(log n)
getMax	O(n)	O(1)
extractMax	O(n)	O(log n)

The heap wins whenever getMax/extractMax are frequent. Full code is in the Approaches selector below.

Summary

Key takeaway

Array with the max at index 0. insert appends + sifts up; extractMax swaps the last element to the root + sifts down toward the larger child; getMax reads index 0. insert/extract are O(log n), getMax is O(1).

insert(x):    append x; while x > parent: swap up
extractMax(): m = arr[0]; arr[0] = arr.pop(); sift down toward larger child; return m