Max Heap

A max heap has the same complete-tree shape as a min heap, but the comparison is reversed. Every parent must be greater than or equal to each child, so values get no larger as you move downward. The root is therefore the maximum element.

The array layout is unchanged: index i has children 2i+1 and 2i+2, and parent (i-1)/2. Only the direction of comparison changes. For example, [9,7,8,2,6] is a valid max heap because each parent dominates its children, even though the array is not globally sorted.

Insertion appends the new value and then sift-up swaps while the child is larger than the parent. Removing the maximum swaps the root with the last element, shrinks the heap, and sift-down swaps with the larger child until the property is restored.

The height argument is the same as for a min heap. A complete tree with n elements has height O(log n), so offer() and poll() are O(log n), while peek() remains O(1).

Java's PriorityQueue is a min heap by default, so the smallest item according to the comparator is returned first. To model a max heap, reverse the natural order with Collections.reverseOrder() or provide a comparator that treats larger values as higher priority.

Avoid subtraction comparators such as b - a when values can be large. Integer overflow can reverse the ordering and silently corrupt the heap. Prefer Integer.compare(b, a) for descending integer order or a comparator built from safe comparison helpers.

Max heaps are useful when the largest remaining item should be served next, such as repeatedly taking the most frequent task, the largest profit, or the current upper half boundary in a median structure. They are also used as the opposite half of a two-heap design.

In top-k interviews, be careful with direction. To keep the k largest items efficiently, a size-k min heap is often better than a max heap because the root is the smallest kept item. A max heap is right when you truly need to remove the largest next.