Max heap

As explained in Advanced Algorithms and Data Structures

A max-heap is a heap-ordered tree in which every parent has a key greater than or equal to those of its children, making the maximum element accessible at the root.

A max heap is a priority-queue structure in which larger priorities come first: every parent has a key greater than or equal to its children, so the maximum element remains at the root. It suits tasks where the next item must have the highest priority. section 2.5.4

A typical array-backed max heap supports these operations:

• Insert an element and restore heap order by moving it upward. section 2.6.4
• Read or remove the root with top(). Replace the root with the last array element, then push it down until the heap property is restored. section 2.6.4
• Choose a min heap instead when the smallest priority should be returned first; the implementations are symmetric, or priorities can be negated. section 2.5.4

Selecting the largest elements

To extract the largest k elements from a static set of n values, build a max heap with heapify in O(n), then call top() k times. This uses O(n) extra space and costs O(n + k log n). When n is much larger than k, a max heap is wasteful for this task: a size-k min heap keeps the largest values found so far and exposes the smallest retained value for replacement. section 2.7.1 section 2.7.2

Figure 2.10 Removing the top element from a binary heap. (A) From a valid ternary heap, we remove the root of the heap (storing it in a temporary location, in order to return it at the end). (B) We replace the old root with the last element in the array (which is also removed from its tail). The new root might violate heap’s properties (and it does, in this example), so we need to push it down, comparing it to its children to check that the heap’s properties are not violated. (C) We move the new root down toward the heap’s leaves, until we find a valid spot for it (that is, the first one that does not violate the heap’s properties).

Trace root removal, replacement by the last array element, and pushDown through the heap until the new root reaches a valid position. section 2.6.4

How Advanced Algorithms and Data Structures covers it

How deep it goes

Explains ordering, root removal, replacement, pushDown, and logarithmic operation costs, while deferring full implementation details.

Examples

Uses prioritized tasks, tuple ordering, root-removal diagrams, and largest-k selection from 2, 4, 1, 3, 7, and 6.

What it assumes

Assumes familiarity with priority queues, arrays, and asymptotic running time while defining min-heap and max-heap ordering.

What you can do after

Operate/configure a max heap for highest-priority extraction and choose a bounded min-heap when selecting a small largest subset.

How it connects

Connects priority queues with min-heaps, heapify, array representations, and d-way heaps.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

• heapkind of · A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.
• min-heapcontrasts with · A min-heap is a heap-ordered tree in which each parent has no greater priority than its children, so a minimum-priority element is at the root.
• heapifyproduced by · Heapify is the process of rearranging an unordered collection to satisfy the invariant of a valid heap.
• bubble upuses · Bubble up is a heap-repair technique that moves an element toward the root until the heap-ordering property is restored.
• linear time complexityuses · Linear time complexity is an asymptotic running-time growth rate proportional to input size, or to the combined sizes of multiple inputs, up to a constant factor.
• priority queueaddressed by · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.