Heaps, Priority Queues and Disjoint Sets

Introduction

Many algorithms must repeatedly select the smallest or largest item, maintain dynamically changing priorities, or determine whether two objects belong to the same connected group. Ordinary arrays, linked lists, and balanced search trees can solve these problems, but specialized structures often provide better performance and simpler algorithms.

A heap supports efficient access to an extreme element. A priority queue is an abstract data type built commonly with a heap. A disjoint-set structure, also called union–find, maintains a collection of non-overlapping sets and efficiently supports connectivity operations. These structures are fundamental in operating-system scheduling, event simulation, graph algorithms, clustering, networking, and machine-learning systems.

This chapter develops binary heaps, d-ary and specialized heaps, priority queues, amortized analysis, and disjoint sets. The emphasis is on implementation, complexity analysis, and appropriate structure selection.

Learning Objectives

After studying this chapter, a student should be able to:

1. Explain the heap-order and shape properties of binary heaps.

2. Implement insertion, deletion, and construction operations for min-heaps and max-heaps.

3. Analyze worst-case and amortized running times.

4. Select and use priority queues in scheduling and graph algorithms.

5. Explain binomial and Fibonacci heaps and identify when they are useful.

6. Implement disjoint sets using union by rank or size and path compression.

7. Apply union–find to clustering and minimum spanning tree algorithms.

8. Evaluate practical trade-offs involving memory, constants, stability, and implementation complexity.

1. Priority-Based Data Access

A priority queue stores elements with associated priorities. Unlike a queue, which removes the oldest element, a priority queue removes an element with minimum or maximum priority. A min-priority queue returns the smallest key; a max-priority queue returns the largest.

Typical operations are:

• insert(x): add an item.
• peek(): return, but do not remove, the extreme item.
• extract-min or extract-max: remove and return the extreme item.
• decrease-key or increase-key: change an item’s priority in the appropriate direction.
• delete(x): remove a specified item.
• merge: combine two priority queues.

The abstract data type does not dictate its implementation. Arrays, linked lists, balanced trees, and heaps are possible choices. The best choice depends on the operation mix.

2. Binary Heaps

A binary heap is a nearly complete binary tree satisfying a heap-order property.

A min-heap satisfies

`key(parent) ≤ key(child)`

for every parent-child pair. Consequently, the root contains a minimum key. A max-heap uses the reverse relation, so the root contains a maximum key. Equal keys are allowed; heap order is not necessarily strict.

The shape property states that every level is full except possibly the last, and nodes on the last level are filled from left to right. This makes an array representation possible without storing explicit pointers.

For a zero-based array, the relationships are:

• parent(i) = floor((i − 1)/2), for i > 0
• left(i) = 2i + 1
• right(i) = 2i + 2

For a one-based array, the relationships are parent(i) = floor(i/2), left(i) = 2i, and right(i) = 2i + 1. The array length is the number of elements, while the capacity is the allocated storage space.

Height of a binary heap

A heap containing n nodes has height `floor(log₂ n)` when height is measured as the number of edges on a longest root-to-leaf path. Therefore, operations that move along one path take O(log n) time. The logarithm is base 2 because the structure is binary, although the base is usually omitted in asymptotic notation.

3. Core Binary-Heap Operations

Peek

The extreme item is at index 0. Thus peek takes Θ(1) time, assuming the heap is nonempty.

Sift-up and insertion

To insert a key, place it at the next unused array position. This preserves the shape property but may violate heap order with its parent. Repeatedly exchange the item with its parent while it has a smaller key in a min-heap, or a larger key in a max-heap. This procedure is called sift-up, bubble-up, or percolate-up.

The item moves at most one level per iteration, so insertion takes O(log n) worst-case time and Θ(1) best-case time when no movement is required. The additional space is O(1), excluding possible array resizing.

Pseudocode for a min-heap is:

```

insert(x):

append x to the array

i = last index

while i > 0 and A[parent(i)] > A[i]:

swap A[i] and A[parent(i)]

i = parent(i)

```

Extract-min and sift-down

To remove the minimum from a min-heap, save the root, move the last element to index 0, reduce the heap size, and restore heap order. At each step, compare the current item with its smaller child. If the child is smaller, exchange them and continue downward. This is sift-down or heapify-down.

The operation follows one root-to-leaf path and therefore takes O(log n) worst-case time. Peek is not the same as extraction: peek does not modify the structure, whereas extraction does.

```

extractMin():

if heap is empty: report underflow

result = A[0]

A[0] = A[last]

remove last array position

siftDown(0)

return result

```

When the current node has two children, the smaller child must be selected. Choosing the other child can leave a heap-order violation.

Decrease-key and delete

In a min-heap, decreasing a key can violate heap order with its parent, so it is repaired by sift-up. Increasing a key may violate order with a child and is repaired by sift-down. Each takes O(log n), provided the item’s location is known.

Deleting an item efficiently requires either its index or an auxiliary mapping from item identifiers to heap positions. One approach replaces the item with the last element, reduces the size, and then performs either sift-up or sift-down, depending on the new key’s relationship to its neighbors. The worst-case time is O(log n).

4. Building a Heap

There are two important construction methods.

Repeated insertion

Starting with an empty heap and inserting n items takes O(n log n) in the worst case because each insertion can cost O(log n). This method is useful when items arrive incrementally.

Bottom-up heap construction

Given an arbitrary array, all leaves already satisfy heap order because they have no children. Starting with the last internal node and applying sift-down to each internal node constructs a heap:

```

for i = floor(n/2) − 1 down to 0:

siftDown(i)

```

The running time is Θ(n), not Θ(n log n). The reason is that most nodes are near the leaves and can move only a short distance. More formally, if height h nodes are counted and each costs O(h), the total is bounded by a convergent weighted sum proportional to n. This result assumes a standard array-based binary heap and a linear-time sift-down implementation.

Heapsort

To sort in ascending order, build a max-heap and repeatedly exchange the root with the final unsorted position, reduce the heap size, and sift down. Heap construction takes Θ(n), and n extractions take O(n log n), giving Θ(n log n) overall. In-place heapsort uses O(1) auxiliary array space, but it is not stable and often has poorer cache behavior than quicksort or mergesort.

5. Priority Queues in Practice

A heap-based priority queue provides the following typical bounds:

| Operation | Binary min-heap |

|---|---:|

| peek-min | Θ(1) |

| insert | O(log n) |

| extract-min | O(log n) |

| decrease-key | O(log n) |

| build from array | Θ(n) |

| merge | O(n), ordinarily |

A binary heap is usually the default implementation because it is compact, robust, and cache-friendly. A linked implementation may avoid array resizing but loses locality and is more complex.

Stability and tie handling

A heap does not guarantee that equal-priority items are removed in insertion order. If stable behavior is required, store a pair `(priority, sequenceNumber)` and compare sequence numbers when priorities tie. In scheduling systems, this can ensure reproducible behavior.

Resizing

A dynamic array generally doubles its capacity when full. Although one expansion costs Θ(n), the total cost of a sequence of n append operations is Θ(n), so the amortized cost per append is Θ(1). This is an example of amortized analysis: an occasional expensive operation is distributed over many inexpensive operations. Heap insertion remains O(log n) for structural adjustment; resizing adds an amortized O(1) component.

6. Specialized Heaps

d-ary heaps

A d-ary heap has up to d children per node. Its height is Θ(log_d n). In a min d-ary heap, finding the smallest child during sift-down may require up to d comparisons per level. Increasing d reduces height but increases child-selection work. Such heaps can be useful when decrease-key operations are frequent and memory locality matters. The choice of d is an engineering trade-off rather than a universally optimal rule.

Binomial heaps

A binomial heap is a collection of binomial trees satisfying heap order and containing at most one tree of each degree. Its main advantage is efficient merging. With an appropriate root-list representation, merge and insertion can be supported in O(log n), while find-min is O(log n) unless a minimum pointer is maintained. Binomial heaps are conceptually important because their tree structure supports efficient union.

Fibonacci heaps

A Fibonacci heap is a collection of heap-ordered trees with a deliberately lazy strategy. Consolidation is postponed until extract-min. With amortized analysis, its standard bounds include:

• insert: O(1) amortized
• find-min: O(1) amortized
• decrease-key: O(1) amortized
• meld: O(1) amortized
• extract-min: O(log n) amortized

The phrase “amortized” means that the bound applies to a sequence of operations, not necessarily to every individual operation. A Fibonacci heap can improve the theoretical bound of algorithms with many decrease-key operations, such as some implementations of Dijkstra’s algorithm. However, pointer overhead, poor locality, implementation complexity, and large constants often make binary or d-ary heaps faster in practical software.

7. Worked Example: Event Scheduling

Consider a discrete-event simulator with events `(time, eventID)`: `(4,E1)`, `(2,E2)`, `(7,E3)`, and `(2,E4)`. The simulator must process the smallest time first and use eventID as a tie-breaker.

The comparison key is `(time, eventID)`, ordered lexicographically. Thus E2 precedes E4 because both occur at time 2 and `E2 < E4`. A min-heap stores the events. The simulator repeatedly extracts the minimum, processes it, and inserts any newly generated events. Each insertion and extraction costs O(log n), where n is the number of pending events; inspecting the next event costs O(1). This design avoids repeatedly sorting the entire event list after every new event.

8. Disjoint Sets and Union–Find

A disjoint-set data structure maintains a partition of elements into non-overlapping sets. Each element belongs to exactly one set, and no element belongs to two sets. The principal operations are:

• make-set(x): create a set containing only x.
• find(x): return a representative identifying x’s set.
• union(x,y): combine the sets containing x and y.

The representative is an implementation choice; it is not necessarily the smallest or largest element. Two elements are in the same set exactly when their representatives are equal.

A forest representation stores each set as a rooted tree. Each node has a parent pointer. A root is its own parent. Initially, every item is a singleton root.

Naive implementation

A naive union may attach one root beneath the other without considering tree height. Repeated unions can create a chain of n nodes, making find Θ(n). This poor performance motivates balancing techniques.

Union by size or rank

Union by size attaches the smaller tree beneath the larger. Union by rank attaches the root with smaller rank beneath the root with larger rank. Rank is an upper-bound indicator related to tree height; it is not always the exact current height after path compression.

With union by size or rank alone, tree height is O(log n). To see why for union by size: whenever a node’s tree height can increase through attachment, its containing tree at least doubles in size. A node can therefore experience such increases at most log₂ n times.

Path compression

During find(x), path compression makes every node on the search path point directly to the root. The next find on those nodes is consequently much faster.

```

find(x):

if parent[x] != x:

parent[x] = find(parent[x])

return parent[x]

union(x, y):

rx = find(x)

ry = find(y)

if rx == ry: return

attach lower-rank root beneath higher-rank root

```

When path compression is combined with union by rank or size, a sequence of m operations on n elements runs in O(m α(n)) time, where α is the inverse Ackermann function. For all realistic computer sizes, α(n) is at most a very small constant. This bound is amortized and is often described informally as “almost constant time.” It is not literally constant for arbitrary mathematical n.

9. Application: Kruskal’s Minimum Spanning Tree Algorithm

For a connected, weighted, undirected graph, a minimum spanning tree (MST) is a spanning tree with minimum total edge weight. Kruskal’s algorithm sorts edges by nondecreasing weight and considers them in that order. An edge is accepted if its endpoints are currently in different components; otherwise it is rejected because accepting it would create a cycle.

Union–find provides the component test:

1. Make a singleton set for every vertex.

2. Sort all edges by weight.

3. For each edge `(u,v)` in sorted order:

• if find(u) ≠ find(v), add the edge and union(u,v);
• otherwise reject it.

4. Stop after n − 1 edges have been accepted.

If there are V vertices and E edges, sorting costs O(E log E). The union–find operations cost O(E α(V)) amortized, so sorting is normally the dominant term. The algorithm is correct because of the cut property: a lightest edge crossing a cut can safely be included in some MST. When equal weights occur, multiple MSTs may exist, but Kruskal still returns one of minimum total weight.

Small worked example

Suppose edges are AB=1, BC=2, AC=3, CD=4, BD=5. Initially, each vertex is separate. Kruskal accepts AB, then BC. AC is rejected because A and C are already connected. CD is accepted, producing three accepted edges for four vertices. The resulting tree has total weight 1+2+4=7. Edge BD is unnecessary because it would form a cycle.

10. Application: Clustering

Union–find also supports single-linkage clustering. Begin with each data point as its own cluster and process pairwise links from smallest distance upward. A link joins two clusters if they are distinct. Stopping when k components remain yields a clustering threshold determined by the processed distances.

In machine-learning pipelines, the distance computation or edge generation may dominate runtime. Union–find accelerates the connectivity phase but does not eliminate the need to examine or generate candidate pairs. Approximate-nearest-neighbor methods may be used when all pairwise distances are too expensive, but approximation can change the resulting clusters and must be evaluated carefully.

11. Selecting the Appropriate Structure

Use a binary heap when extreme-element operations dominate and a simple, reliable implementation is desired. Use a d-ary heap when the operation mix, cache behavior, or hardware favors fewer levels. Consider binomial or Fibonacci heaps when meld or theoretical decrease-key performance is central and implementation complexity is acceptable.

Use union–find when sets are merged but not split. It is excellent for incremental connectivity, Kruskal’s algorithm, image-region merging, and clustering. It is not suitable for dynamic problems requiring deletion, arbitrary splitting, or shortest-path distances within components.

Balanced search trees may be preferable when ordered traversal, predecessor/successor queries, or deletion by key are required. A heap provides only limited ordering: the root is extreme, but the remaining array is not sorted.

12. Limitations, Reliability, and Governance

Priority-based systems can encode policy. If a scheduler always favors high-priority jobs, low-priority jobs may suffer starvation. Aging—gradually increasing waiting jobs’ priorities—can improve fairness. In safety-critical or regulated settings, priority rules should be documented, auditable, and tested for worst-case behavior.

Tie-breaking affects reproducibility. Parallel implementations may process equal-priority tasks in different orders, potentially producing different outputs when tasks are not independent. Systems should specify whether deterministic ordering is required.

Implementations must handle empty extraction, duplicate keys, integer overflow in index calculations, invalid handles for decrease-key, and concurrent access. A heap is not automatically thread-safe. Locking, ownership rules, or specialized concurrent queues are required in multithreaded environments.

In AI and data-processing systems, these structures influence efficiency but do not guarantee fairness or unbiased outcomes. A priority queue used for data selection can repeatedly favor already well-represented groups. If it affects people or high-impact decisions, designers should assess the policy represented by the priority function, monitor outcomes, and retain appropriate audit records.

13. Best Practices

1. State whether the structure is a min-heap or max-heap.

2. Define tie-breaking rules explicitly.

3. Use bottom-up construction when all initial keys are available.

4. Maintain handles or an index map when arbitrary key updates are required.

5. Distinguish worst-case, expected, and amortized bounds.

6. Test duplicates, empty structures, singleton structures, and already ordered inputs.

7. Prefer union by size or rank together with path compression.

8. Benchmark specialized heaps against binary heaps on representative workloads.

9. Document fairness and starvation policies in scheduling systems.

10. Check invariants after updates: heap shape/order and parent-pointer validity.

Chapter Summary

Heaps exploit a complete-tree shape and a local ordering rule to provide constant-time access to an extreme key and logarithmic insertion and extraction. Array-based binary heaps are compact and generally practical. Bottom-up construction runs in Θ(n), while heapsort runs in Θ(n log n) and uses little auxiliary space. D-ary, binomial, and Fibonacci heaps offer different trade-offs, particularly for merging and decrease-key operations.

Priority queues support scheduling, simulation, graph search, and event processing. Their behavior depends on comparison rules, tie handling, resizing, and fairness policies. Amortized analysis explains why occasional expensive operations, such as array expansion or lazy consolidation, can have a small average cost over a sequence.

Disjoint sets maintain a partition under merging and representative queries. Union by size or rank prevents tall trees, while path compression makes repeated operations almost constant amortized time. These properties make union–find central to Kruskal’s minimum spanning tree algorithm, incremental connectivity, and clustering. Correct structure selection requires attention to operation patterns, memory locality, determinism, scalability, and governance requirements.

Key Terms

Heap: A nearly complete tree satisfying a heap-order property.

Min-heap: A heap whose root contains a minimum key.

Max-heap: A heap whose root contains a maximum key.

Heap order: The rule relating each parent’s key to its children’s keys.

Sift-up: Moving an item toward the root to restore heap order.

Sift-down: Moving an item toward the leaves to restore heap order.

Priority queue: An abstract data type that removes an extreme-priority item.

Decrease-key: An operation that lowers a key in a min-oriented priority queue.

Build-heap: Construction of a heap from an arbitrary array.

Heapsort: An in-place comparison sorting algorithm based on a heap.

d-ary heap: A heap in which each node has up to d children.

Binomial heap: A collection of heap-ordered binomial trees supporting efficient meld.

Fibonacci heap: A lazy heap with strong amortized decrease-key and meld bounds.

Disjoint set: One member of a partition into non-overlapping subsets.

Union–find: A disjoint-set structure supporting find and union.

Path compression: Redirecting find-path nodes directly to their root.

Union by rank: Attaching a lower-rank root beneath a higher-rank root.

Minimum spanning tree: A minimum-weight spanning tree of a connected weighted graph.

Amortized analysis: Analysis of average cost over a sequence of operations.

Inverse Ackermann function: A very slowly growing function appearing in union–find bounds.

Review Questions

Short Answer Questions

1. What are the shape and ordering properties of a binary min-heap?

2. Why does bottom-up build-heap run in Θ(n) time?

3. Distinguish peek-min from extract-min.

4. What is the purpose of path compression?

5. Why can a heap-based priority queue require an explicit tie-breaker?

Long Answer Questions

1. Explain binary-heap insertion and extraction, including their invariants and complexity.

2. Compare binary, d-ary, binomial, and Fibonacci heaps in terms of operations and practical trade-offs.

3. Derive the O(log n) height bound for a binary heap and relate it to heap operations.

4. Explain union by rank, path compression, and the amortized bound for disjoint sets.

5. Describe Kruskal’s algorithm and explain how union–find ensures that cycles are avoided.

Analytical / Application Questions

1. Design a priority queue for a hospital scheduling system. Specify priority fields, tie-breaking, starvation controls, and required operations.

2. Given a graph with weighted edges, trace Kruskal’s algorithm and show the parent or representative changes after every accepted edge.

3. A workload contains millions of insertions, frequent decrease-key operations, and occasional extraction. Compare a binary heap, d-ary heap, and Fibonacci heap, considering both asymptotic bounds and practical implementation costs.

Multiple Choice Questions with Answers

Question 1

Which property guarantees that an array can represent a binary heap without explicit child pointers?

A. Every node has exactly two children

B. The tree is complete, with the last level filled left to right

C. Keys are globally sorted

D. All leaves have equal keys

Correct Answer: B. The tree is complete, with the last level filled left to right

Question 2

What is the worst-case time complexity of extracting the minimum from a binary min-heap containing n elements?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: B. Θ(log n)

Question 3

What is the running time of bottom-up construction of a binary heap from n existing array elements?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 4

Which operation restores heap order by moving an inserted item toward the root?

A. Sift-down

B. Path compression

C. Sift-up

D. Union by rank

Correct Answer: C. Sift-up

Question 5

Why might a priority queue store a sequence number together with each priority?

A. To increase the heap height

B. To provide deterministic or stable tie-breaking

C. To eliminate extraction

D. To convert it into a search tree

Correct Answer: B. To provide deterministic or stable tie-breaking

Question 6

What does union by size do when combining two disjoint-set trees?

A. Attaches the larger tree beneath the smaller

B. Attaches the smaller tree beneath the larger

C. Sorts all elements before merging

D. Deletes both roots

Correct Answer: B. Attaches the smaller tree beneath the larger

Question 7

With union by rank and path compression, a sequence of m disjoint-set operations on n elements has which amortized bound?

A. O(mn)

B. O(m log n)

C. O(m α(n))

D. O(n log m)

Correct Answer: C. O(m α(n))

Question 8

In Kruskal’s algorithm, an edge is rejected when:

A. Its weight is positive

B. Its endpoints already have the same representative

C. It is the first edge considered

D. The graph has more than two vertices

Correct Answer: B. Its endpoints already have the same representative

Question 9

Which heap is especially known for O(1) amortized decrease-key?

A. Binary heap

B. Fibonacci heap

C. Sorted array

D. Binary search tree without balancing

Correct Answer: B. Fibonacci heap

Question 10

For a connected graph with V vertices, how many edges does Kruskal’s algorithm accept into a spanning tree?

A. V − 1

B. V

C. 2V

D. E − 1

Correct Answer: A. V − 1