Priority Queues and Disjoint-Set Structures

Introduction

Many algorithmic problems require more than storing data and retrieving it in the order of arrival. A scheduler must repeatedly select the most urgent task; a graph algorithm must repeatedly choose a least-weight edge or vertex; and a connectivity system must determine whether two objects belong to the same component. Priority queues and disjoint-set structures address these two forms of dynamic selection and dynamic relationship management.

A priority queue maintains elements with associated priorities and supports access to an extreme-priority element, usually the minimum or maximum. A disjoint-set structure, also called union–find, maintains a partition of elements into non-overlapping sets and supports finding a representative of an element's set and merging two sets. Their importance extends from operating systems and network routing to minimum spanning trees, clustering, image processing and event simulation.

This chapter examines binary, binomial, Fibonacci and pairing heaps; union–find with path compression and union by rank; amortized analysis; implementation decisions; and practical applications.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain the abstract operations and invariants of priority queues and disjoint-set structures.
2. Implement and analyse binary, binomial, Fibonacci and pairing heaps.
3. Compare worst-case, amortized and practical performance trade-offs.
4. Explain why path compression and union by rank make union–find nearly constant-time.
5. Apply these structures to scheduling, clustering, connectivity and graph optimization.
6. Select an appropriate structure under constraints involving workload, memory, update frequency and implementation complexity.

1. Priority Queues as Abstract Data Types

A priority queue stores records of the form (key, value), where the key determines priority. In a min-priority queue, a smaller key has higher priority; in a max-priority queue, a larger key has higher priority. Equal keys may be handled in any order unless the implementation explicitly provides stability.

The principal operations are:

A heap is a common implementation. For a min-heap, every parent key is no greater than the keys of its children. This is a local ordering invariant, not a complete sorting invariant: siblings and nodes in different subtrees need not be ordered.

If a complete binary tree is stored in a zero-based array, the relationships are:

The formulas apply when the array contains the heap in level order. The height of a binary heap with n elements is ⌊log₂ n⌋, so upward and downward repairs take O(log n) time.

Building a Binary Heap

Inserting n items individually costs O(n log n) in the worst case. Bottom-up construction, called BUILD-HEAP, starts at the last internal node and applies heapify downward. Its total cost is O(n), not O(n log n). The reason is that most nodes are near the leaves and can move only a small distance. If h is a node's height, the total work is bounded by a sum proportional to:

This result assumes a complete binary-tree layout and constant-time key comparisons.

2. Binary Heaps and Their Engineering Properties

For a binary min-heap, insert places a new element at the next available leaf and repeatedly exchanges it with its parent while its key is smaller. Extract-min removes the root, moves the last element to the root, and repeatedly exchanges it with the smaller child until the invariant is restored.

A binary heap is often the best default priority queue because it has compact storage, excellent cache locality, low constant factors and simple debugging. Its principal weakness is melding: combining two large heaps efficiently is not a native operation in the standard array representation.

A practical implementation should define how handles to elements are maintained. If decrease-key or delete identifies an item by an external object reference, the implementation must either store a pointer to its heap position or maintain an index map. Without such metadata, locating an arbitrary item may cost O(n).

3. Binomial Heaps

A binomial heap is a collection of binomial trees satisfying two properties:

1. Each tree obeys the min-heap order.
2. There is at most one tree of any degree.

A binomial tree Bₖ contains 2ᵏ nodes and has height k. It is formed by linking two Bₖ₋₁ trees, making one root the child of the other. Consequently, a binomial heap with n nodes contains at most ⌊log₂ n⌋ + 1 trees, corresponding to the 1-bits in the binary representation of n.

The central operation is union. Two roots of equal degree are linked, analogous to carrying in binary addition. The root with the smaller key becomes the parent. A linked list of roots is scanned while equal degrees are consolidated.

Binomial heaps are useful when meld is important and worst-case logarithmic behaviour is preferred. Their pointer-rich representation is less cache-friendly than a binary heap, and their implementation is more complex.

4. Fibonacci Heaps and Amortized Analysis

A Fibonacci heap is a collection of heap-ordered trees with a more relaxed structure than a binomial heap. Roots are kept in a circular doubly linked list. Nodes may be marked when they lose a child. Consolidation is delayed until extract-min, allowing inexpensive insertion, meld and decrease-key.

The key design principle is deferred restructuring. Rather than immediately restoring a tightly constrained forest after every operation, the structure records potential disorder and pays for consolidation later. The amortized cost is analysed using a potential function. A common potential is:

where t(H) is the number of trees in heap H and m(H) is the number of marked non-root nodes. The amortized cost of an operation is:

Here cᵢ is the actual cost of operation i, Dᵢ is the data structure after it, and Φ is nonnegative. Over any sequence, the total actual cost is at most the total amortized cost plus the initial potential.

For a Fibonacci heap, the standard bounds are:

The decrease-key operation cuts a node from its parent when heap order is violated and may cascade upward. Marking ensures that a non-root node cannot lose too many children without being cut. This restriction implies that a node of degree d has a subtree size growing exponentially with d; therefore the maximum degree is O(log n).

The attractive theoretical bound for decrease-key matters in algorithms such as Dijkstra's and Prim's when the number of decrease-key operations is large. However, Fibonacci heaps have substantial pointer and allocation overhead. For many real workloads, binary or pairing heaps are faster despite weaker asymptotic bounds.

5. Pairing Heaps

A pairing heap is a self-adjusting, heap-ordered multiway tree. Its basic operations are simple. To meld two heaps, compare their roots and make the larger-root tree a child of the smaller-root tree. Insertion melds a singleton with the existing heap. Extract-min removes the root and combines its children, commonly in two passes: pair adjacent children from left to right, then meld the resulting heaps from right to left.

Pairing heaps are attractive because they combine a simple implementation with strong practical performance. Their exact theoretical bounds depend on the operation variant and the analysis model. It is safe to state that insert, meld and find-min are O(1) amortized in the usual implementation, while extract-min is O(log n) amortized. Decrease-key has good empirical performance, but its precise asymptotic bound is more subtle than the classical Fibonacci-heap bound and should not automatically be claimed as O(1) amortized for every pairing-heap variant.

This distinction illustrates an important professional principle: empirical speed, amortized guarantees and worst-case guarantees are different claims. A design should identify which one is required.

6. Comparative Selection of Heap Structures

The correct choice depends on the operation mix. If extract-min dominates and the data fit in memory, a binary heap is usually compelling. If many independent queues must be combined, a meldable heap is preferable. If theoretical decrease-key performance is central and implementation complexity is acceptable, a Fibonacci heap may be justified. Pairing heaps are a strong practical alternative when a simple meldable design is desired.

7. Disjoint Sets and the Union–Find Abstraction

A disjoint-set data structure maintains a partition of a universe U. Initially, each element is in a singleton set. The operations are:

• MAKE-SET(x): create a set containing x.
• FIND(x): return a representative of the set containing x.
• UNION(x, y): merge the sets containing x and y, if they are distinct.

The data structure must preserve three properties: sets remain disjoint, every element belongs to exactly one set, and each set has one representative at any time. The representative is not necessarily semantically meaningful; it is simply an identifier for the component.

A forest representation stores each element as a node with a parent pointer. A root is identified by parent[x] = x. FIND follows parent pointers to the root. UNION links one root beneath another.

Union by Rank

If roots are linked arbitrarily, a sequence of unions can create a chain of n nodes, making FIND O(n). Union by rank prevents this. Each root stores an upper bound on tree height, called rank. The smaller-rank root is attached under the larger-rank root. If ranks are equal, either root may become parent and the new root's rank increases by one.

Rank is not necessarily the current height after path compression; it remains a conservative structural bound used to guide linking.

Path Compression

Path compression changes FIND. After locating the root, it makes every node visited on the path point directly to that root. A recursive form is:

FIND(x):
    if parent[x] ≠ x:
        parent[x] ← FIND(parent[x])
    return parent[x]

Path compression is correct because it changes only parent pointers within the same set. It reduces future search paths without changing the partition.

8. Complexity of Union–Find

With union by rank alone, the forest height is O(log n). With path compression alone, the worst-case cost of an individual operation can still be large, although sequences often perform well. Used together, union by rank and path compression give a total time of:

for m MAKE-SET, UNION and FIND operations on n elements, where α is the inverse Ackermann function. For all practical input sizes, α(n) is at most a very small constant. This is not literally O(1) in the formal asymptotic sense, but it is effectively constant for practical systems.

The bound is amortized over a sequence, not necessarily a worst-case guarantee for every individual operation. It also assumes the standard forest implementation and the stated heuristics. If a system requires a strict per-operation worst-case bound, another structure or scheduling policy may be necessary.

Union by size is an alternative to union by rank. It attaches the smaller set under the larger and gives the same asymptotic bound when combined with path compression. Size can be more intuitive when component cardinalities are useful to the application.

9. Applications

9.1 Scheduling and Event Simulation

A discrete-event simulator maintains future events ordered by timestamp. The next event is extracted, and newly generated events are inserted. A binary heap provides O(log n) insertion and extraction with low overhead. If multiple simulation engines frequently combine event queues, a meldable heap can be advantageous.

Schedulers may use composite priorities such as deadline, class and arrival sequence. A key can be represented as a tuple ordered lexicographically. The policy must specify tie-breaking, starvation prevention and whether priorities may change. A priority queue implements selection; it does not itself guarantee fairness.

9.2 Shortest Paths and Minimum Spanning Trees

Dijkstra's algorithm repeatedly extracts the unsettled vertex with minimum tentative distance and performs relaxations. Prim's algorithm repeatedly extracts the minimum-weight boundary edge or vertex. With a binary heap, a typical sparse-graph implementation runs in O((V + E) log V), assuming adjacency lists and at most O(E) priority updates. With a Fibonacci heap, the classical bound is O(E + V log V), because decrease-key is O(1) amortized. Here V is the number of vertices and E is the number of edges.

These bounds do not imply that Fibonacci heaps always win. Graph representation, edge density, cache effects, allocation cost and the number of successful relaxations affect actual performance. Negative edge weights invalidate Dijkstra's algorithm, regardless of the heap used.

9.3 Kruskal's Minimum Spanning Tree Algorithm

Kruskal's algorithm sorts edges by nondecreasing weight and scans them. An edge (u, v) is accepted if FIND(u) and FIND(v) return different representatives; then UNION(u, v) merges the components. With an efficient comparison sort, the total running time is:

The first term is sorting, and the second is the disjoint-set work. The equality in the final expression expresses asymptotic dominance, not numerical equality. Union–find prevents cycles while preserving the greedy choice that leads to a minimum spanning forest.

9.4 Clustering and Connectivity

In single-linkage clustering, edges are considered in increasing distance order. Components are merged when an edge connects different components. Union–find provides efficient component maintenance, while a priority queue or sorted edge list determines the next candidate. In network monitoring, FIND can answer whether two devices are currently connected under a sequence of link additions. Standard union–find does not efficiently support arbitrary deletions; dynamic connectivity with deletions requires more advanced structures.

9.5 Image Processing and Percolation

Pixels or cells can be treated as vertices, with unions representing adjacency or similarity. Connected-component labelling uses union–find to identify regions. A priority queue can process pixels by intensity or edge weight. Applications must consider memory layout, parallelism and the semantic consequences of the chosen adjacency relation.

10. Illustrative Case: Emergency Logistics Network

This fictional case illustrates the combined use of both structures.

Background

A regional emergency system receives supply requests from hospitals. Each request has a deadline and urgency score. The road network may become partitioned by damage, while repairs progressively reconnect locations.

Problem

The system must select the next request for dispatch, determine whether a hospital is connected to a warehouse, and update connectivity as roads are repaired. Requests can have their urgency increased when a medical condition deteriorates.

Approach

A min-priority queue stores requests using the key (deadline, −urgency, arrival sequence). The first field ensures deadlines dominate; the second gives higher urgency priority among equal deadlines; the third provides deterministic tie-breaking. A binary heap is selected because extraction and insertion dominate, and the system has no frequent queue-meld operation.

A disjoint-set structure stores locations. Each repaired road invokes UNION(u, v). A route query invokes FIND(hospital) and FIND(warehouse); equality of representatives indicates connectivity. Union by size and path compression are used.

If a request's key changes, the implementation either performs decrease-key through a maintained handle or inserts a new version marked with a request identifier and ignores stale entries when extracted. The latter technique is often simpler but can increase memory use.

Outcome

Priority selection takes O(log r) per insertion or extraction for r active entries. Connectivity operations take O(α(N)) amortized over a sequence involving N locations. The system remains responsive as the number of roads and requests grows, provided stale queue entries are bounded or periodically rebuilt.

Learning Points

The queue and the disjoint-set structure solve different problems: one orders pending work, while the other represents equivalence classes. Their combination is powerful, but neither automatically supplies fairness, route optimality, deletion support or fault tolerance. Those requirements must be designed explicitly.

11. Limitations, Governance and Best Practices

Priority queues can suffer from starvation when low-priority items are continually bypassed. Ageing, quota policies or multi-level scheduling can mitigate this. A comparator must be deterministic and consistent; violating transitivity can corrupt heap reasoning.

Union–find is excellent for incremental unions but poorly suited to deletions, split operations and queries requiring the complete members of a component. It also reports equivalence, not path quality. Connectivity must not be confused with reachability in directed graphs or with shortest-path distance.

For production implementations:

1. State whether bounds are worst-case, amortized or expected.
2. Test duplicate priorities, empty structures, singleton sets and repeated UNION operations.
3. Use invariant checks during development: heap order, valid parent roots and rank or size consistency.
4. Avoid recursive FIND if stack depth or language recursion limits are concerns; iterative path halving is an alternative.
5. Benchmark representative workloads rather than relying only on asymptotic notation.
6. Use stable identifiers and audit logs when priority decisions affect people or safety.
7. Protect priority metadata from unauthorized modification, especially in access-control, finance or emergency systems.

Contemporary implementations increasingly consider parallel and distributed settings. Concurrent priority queues require synchronization or relaxed ordering, while distributed union–find requires coordination and may face stale state. GPU connected-component algorithms often replace pointer-heavy structures with array-based techniques. These adaptations preserve the underlying concepts but change the performance model.

Chapter Summary

Priority queues support ordered selection through operations such as insert, extract-min and decrease-key. Binary heaps are compact and practical; binomial heaps provide efficient melding with logarithmic bounds; Fibonacci heaps achieve excellent amortized decrease-key performance through lazy consolidation; and pairing heaps offer a simple, effective meldable alternative whose exact bounds depend on the variant.

Amortized analysis distributes the cost of occasional expensive operations across a sequence, commonly using a potential function. Union–find represents a partition through parent forests. Union by rank or size limits tree growth, while path compression flattens search paths. Together they provide O(m α(n)) total time for m operations on n elements.

These structures are central to scheduling, event simulation, shortest paths, minimum spanning trees, clustering and incremental connectivity. Selection must account for operation mix, memory locality, implementation complexity, update semantics and application requirements such as fairness, deletion or auditability.

Key Terms

Priority queue: An abstract data type that returns an element with extreme priority.

Heap: A partially ordered tree-based structure used to implement priority queues.

Heap order: The invariant that each parent has priority no lower than its children in a min-heap.

Binary heap: A complete binary heap usually stored in an array.

Heapify: The process of restoring heap order by moving a node upward or downward.

Binomial tree: A recursively defined tree containing 2ᵏ nodes at degree k.

Binomial heap: A collection of at most one heap-ordered binomial tree of each degree.

Fibonacci heap: A lazily consolidated collection of heap-ordered trees with strong amortized bounds.

Pairing heap: A self-adjusting, heap-ordered multiway tree.

Meld: The operation of combining two priority queues.

Amortized analysis: Analysis of average cost over a sequence, without assuming probabilistic inputs.

Potential function: A stored measure of structural disorder used in amortized analysis.

Disjoint-set structure: A data structure maintaining a partition of elements.

Union–find: Another name for a disjoint-set structure supporting FIND and UNION.

Representative: The root identifier used to denote a set.

Path compression: A FIND optimisation that makes visited nodes point directly to the root.

Union by rank: Linking the lower-rank root beneath the higher-rank root.

Inverse Ackermann function: An extremely slowly growing function appearing in the union–find complexity bound.

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

Connectivity: The property of belonging to the same component under specified relationships.

Review Questions

Short Answer Questions

1. What invariant distinguishes a min-heap from a sorted array?
2. Why does bottom-up BUILD-HEAP run in O(n) time?
3. What is the purpose of consolidation in a Fibonacci heap?
4. How does path compression change a union–find forest?
5. Why is union–find unsuitable for arbitrary edge deletions?

Long Answer Questions

1. Compare binary, binomial, Fibonacci and pairing heaps in terms of operations, asymptotic bounds and practical trade-offs.
2. Explain the potential-function analysis of Fibonacci heaps and define each term in the potential function.
3. Describe union by rank and path compression, and explain the significance of O(m α(n)).
4. Analyse the use of priority queues in Dijkstra's algorithm, including assumptions about edge weights and graph representation.
5. Explain Kruskal's algorithm and derive its overall asymptotic running time.

Analytical / Application Questions

1. Design a scheduler for tasks whose deadlines and urgency values may change. Choose a priority-queue strategy and justify how stale entries or decrease-key operations will be handled.
2. A network receives only link additions and connectivity queries. Select a disjoint-set representation, specify the operations, and explain how its performance changes if path compression is omitted.
3. For a sparse graph with many successful decrease-key operations and severe memory-locality constraints, evaluate whether a Fibonacci heap is necessarily preferable to a binary or pairing heap. Justify the decision using both asymptotic and engineering considerations.

Multiple Choice Questions with Answers

Question 1

Which operation is O(1) in a standard binary min-heap?

A. find-min

B. extract-min

C. decrease-key

D. meld

Correct Answer: A. find-min

Question 2

What is the principal reason that bottom-up BUILD-HEAP runs in O(n) time?

A. Every node moves exactly one level

B. Most nodes are close to the leaves and can move only a short distance

C. The heap is already sorted

D. Heapify uses hashing

Correct Answer: B. Most nodes are close to the leaves and can move only a short distance

Question 3

In a Fibonacci heap, what does the potential function commonly count?

A. Only the number of keys

B. The number of array positions

C. Trees and weighted marked non-root nodes

D. Only the maximum key

Correct Answer: C. Trees and weighted marked non-root nodes

Question 4

What does union by rank do when two roots have different ranks?

A. Attaches the higher-rank root below the lower-rank root

B. Attaches the lower-rank root below the higher-rank root

C. Deletes the lower-rank root

D. Rebuilds every tree from scratch

Correct Answer: B. Attaches the lower-rank root below the higher-rank root

Question 5

What is the combined amortized complexity of m union–find operations on n elements with path compression and union by rank?

A. O(mn)

B. O(m log n)

C. O(m α(n))

D. O(n² log m)

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

Question 6

Which algorithm uses union–find to reject edges that would create cycles?

A. Dijkstra's algorithm

B. Kruskal's algorithm

C. Binary search

D. Topological sorting

Correct Answer: B. Kruskal's algorithm

Question 7

Why can a binary heap be preferred to a Fibonacci heap in practice?

A. It always supports faster meld

B. It has compact storage and better cache locality

C. It provides constant-time worst-case extract-min

D. It does not require comparisons

Correct Answer: B. It has compact storage and better cache locality

Question 8

What does FIND(x) return in a disjoint-set structure?

A. The shortest path from x

B. The minimum key in the universe

C. A representative of x's set

D. The number of elements in x's set

Correct Answer: C. A representative of x's set

Question 9

For a connected graph with V vertices and E edges, what is the classical binary-heap bound for sparse-graph Dijkstra implementation?

A. O(V + E) for arbitrary nonnegative weights

B. O((V + E) log V)

C. O(V²E)

D. O(log E)

Correct Answer: B. O((V + E) log V)

Question 10

Which statement about standard union–find is correct?

A. It efficiently supports arbitrary deletions

B. It maintains shortest-path distances

C. It is well suited to incremental unions and connectivity queries

D. It requires elements to be stored in sorted order

Correct Answer: C. It is well suited to incremental unions and connectivity queries