Ordered trees and priority heaps

Prerequisites: Binary trees, arrays, recursion, and logarithms.

Learning objectives

• State the search-tree and heap invariants.
• Trace a rotation and a heap operation.
• Choose a structure from required queries.

Order is not one universal property

A binary search tree orders every key in a node’s left subtree before the node and every key in its right subtree after it, with an explicit duplicate policy. Searching follows one child after each comparison. A height-h tree therefore needs O(h) comparisons. Inserting sorted keys into an unbalanced tree can create a chain of height n, making searches linear.

Balanced search trees maintain extra structural constraints so height remains O(log n). A rotation changes local parent-child relationships while preserving inorder key order. Suppose 20 has left child 10, and 10 has subtrees A and B while 20 has right subtree C. A right rotation makes 10 the parent, places 20 as its right child, and moves B to become 20’s left subtree. The ordering A,10,B,20,C remains intact. Rebalancing must also update metadata such as heights, colors, or subtree sizes.

A heap promises only a next priority

A binary min-heap stores a complete binary tree, commonly in an array. For zero-based index i, children are 2i+1 and 2i+2. Its invariant is that each parent’s key is no greater than either child’s. This guarantees that the root is minimal, but it does not order siblings or arbitrary subtrees. Searching for an arbitrary key may still require linear work.

Insert 2 into the min-heap [3,5,4,9,8]. Append it at index 5, compare with its parent at index 2 containing 4, and swap. Compare again with the root containing 3 and swap. The result is [2,5,3,9,8,4]. Each swap restores the violated parent edge while leaving unaffected subtrees valid. The number of upward moves is at most the tree height, O(log n).

Removing the minimum replaces the root with the last element and sifts it down, swapping with the smaller child until the invariant holds. Constructing a heap bottom-up is linear, even though repeated independent insertions give an O(n log n) bound: most nodes are close to leaves and need little work.

Add metadata deliberately

A balanced search tree augmented with subtree sizes can support rank and select. Every rotation must preserve both search order and the metadata equations. A heap can support efficient priority changes if a separate index records where each item currently resides; every swap must update that index. Additional capabilities create additional invariants.

For a scheduler that needs the next deadline, a heap is a direct fit. For listing all events between two timestamps in sorted order, a balanced ordered tree is more natural. Compare these structures in Open Data Structures, then state the exact query each invariant makes cheap.

Practice problem

Start with min-heap [2,5,3,9,8,4]. Remove the minimum, showing the replacement and each swap. Then explain why a heap lookup for value 8 cannot simply choose left or right as in a search tree. For the rotation described in the reading, give valid numeric keys for A, B, and C and verify the inorder order before and after.

Worked solution

Replace root 2 with final element 4 and remove the old last slot: [4,5,3,9,8]. The smaller child is 3 at index 2, so swap to obtain [3,5,4,9,8]. That node has no children, so the operation ends. Heap order gives only parent≤child; both subtrees may contain values larger than the root, so comparing 8 with the root does not identify one unique subtree. For the rotation, A may contain 5, B may contain 15, and C may contain 30. The inorder traversal remains [5,10,15,20,30], demonstrating that the rotation preserves ordering while changing height.

Check your understanding

A min-heap stores[2,5,3,9,8,4]. After removing 2 and restoring the heap with the last element, which array is valid for the stated sift-down trace?

• [4,5,3,9,8]
• [3,4,5,8,9]
• [3,5,4,9,8]
• [5,3,4,9,8]

Explanation

Move 4 to the root, compare children 5 and 3, then swap with 3. The remaining array need not be fully sorted.

Right-rotate node 20 whose left child is 10 and whose child 10 has right subtree rooted at 15. Where must subtree 15 go?

• Become the left subtree of 20.
• Become the right subtree of 20.
• Be discarded because it lies between the rotated keys.
• Remain the right child of 10.

Explanation

Every key in that subtree is greater than 10 and less than 20, so it becomes 20’s left subtree while preserving inorder order.

Primary reading

• Open Data Structures: Pat Morin, open textbook

Open the study and save your work →