Heap invariant

As explained in Advanced Algorithms and Data Structures

A heap invariant is the ordering condition requiring each node's priority to be properly ordered relative to the priorities of its parents or children.

A priority queue must return the highest-priority item currently stored. A heap makes that possible by requiring every node to have at least as high a priority as its children. The root therefore has the highest priority in the whole heap. In a min-heap, smaller priority values rank higher; in a max-heap, larger values rank higher. section 2.5.3 section 2.5.5

Keep the ordering rule separate from the heap’s structural rules. A binary heap has at most two children per node and forms a complete, left-adjusted tree. These structural invariants let an array store its nodes from top to bottom, left to right, without parent or child pointers. With zero-based indices, node i has children at 2i+1 and 2i+2; a non-root node’s parent is at floor((i−1)/2). section 2.5.3

Figure 2.4 A binary heap. Only priorities are shown for the nodes (elements are irrelevant here).The numbers inside the small squares show the indices of the heap elements in the array. Nodes are matched into array elements top to bottom, left to right. Top: the tree representation for the heap. Notice how every parent is smaller than (or at most equal to) its children and, in turn, all elements in its subtree. Bottom: the same heap in its array representation.

Compare each parent with its children, then follow the same nodes into their array positions. section 2.5.3

Operations preserve the structure but may temporarily break priority ordering:

• Insert: append the new item, then bubble it up while it outranks its parent. In a D-way heap, this takes at most logD(n) swaps. section 2.6.3
• Remove or change a priority: push an item down if a child outranks it; an increased priority may instead require bubbling up. section 2.6 section 2.6.3
• Heapify an array: visit internal nodes from right to left, pushing each down after its children’s sub-heaps are valid. section 2.6.7

The same ordering rule works for a D-way heap: each node has at most D children, while the tree remains complete and left-adjusted. In a zero-based array, node i’s children occupy positions Di+1 through D(i+1), and a non-root node’s parent is at floor((i−1)/D). Changing the branching factor changes how many children a repair step must consider. section 2.5.5 section 2.6.7

When a repair order matters

Suppose an update raises the priorities of both a parent and its child to the same value. If the child is bubbled up first, it stops at its equal-priority parent. Bubbling the parent up afterward can leave the child beneath a lower-priority node. Updating duplicate occurrences requires an order that restores the invariant for all of them, such as left-to-right bubble-up calls. section 2.6.6

A treap also enforces a heap invariant on priorities, alongside binary-search-tree ordering on keys. When insertion places a key correctly but its priority outranks its parent, rotations move it upward: swapping nodes as in an array heap would not serve the tree’s key ordering. Deletion can likewise rotate a node downward until it becomes a removable leaf. section 3.3.4 section 3.3.5

How Advanced Algorithms and Data Structures covers it

How deep it goes

Develops array index rules and bubble-up, push-down, and heapify repairs, including an update-order failure with duplicates.

Examples

Uses indexed heap diagrams, a ternary-heap insertion, bottom-up heapification, and a duplicate-priority update failure.

What it assumes

Assumes basic arrays and tree nodes while defining completeness, branching factor, and parent-child index relationships.

What you can do after

Diagnose/debug with it when insertion, removal, or priority updates leave a parent ordered incorrectly against a child.

How it connects

Links priority queues, complete trees, array representation, D-way heaps, heapify, and treap rotations.

liveBookmanning.com

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

Related concepts

• tree rotationaddressed by · A tree rotation is a local restructuring operation that changes parent-child relationships while preserving the in-order sequence of a binary search tree.
• pushdown operationimplemented by · A pushdown operation restores heap ordering by repeatedly moving an element toward the leaves and exchanging it with a higher-priority child when necessary.
• bubble upaddressed by · Bubble up is a heap-repair technique that moves an element toward the root until the heap-ordering property is restored.
• helper functionused by · A helper function is a reusable supporting function that performs an operation for a larger computation or other code.
• heapconfigures · 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.
• invariantkind of · An invariant is a property or condition that remains true across the valid states, operations, or specified transformations of a system or computation.

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.