Binomial Heap

Definition

Concept

Binomial heap: a collection of binomial trees satisfying heap property. Purpose: implement priority queues efficiently. Key feature: fast merge (union) of two heaps.

Heap Property

Min-heap: every node’s key ≤ children’s keys. Ensures minimum element at root of some tree in heap. Enables efficient minimum retrieval.

Comparison

Compared to binary heap: binomial heap supports quicker merges. Suitable for applications requiring frequent union operations.

"The binomial heap structure allows merging of two heaps in O(log n) time, outperforming binary heaps in union operations." -- J. Vuillemin

Structure

Composition

Binomial heap: set of binomial trees, each tree order unique. No two trees of same order coexist. Represents heap as forest, not single tree.

Forest Representation

Trees arranged in ascending order of degree. Linked by root list pointers. Each tree corresponds to a bit in binary representation of heap size.

Node Layout

Nodes store key, pointer to parent, child, and sibling. Child pointer points to leftmost child. Siblings linked as linked list.

Binomial Trees

Definition

Binomial tree Bk: defined recursively. B0 single node. Bk formed by linking two Bk-1 trees.

Properties

Size: 2^k nodes. Height: k. Number of nodes at depth d: C(k, d) (binomial coefficient). Root degree: k.

Linking Operation

Two Bk-1 trees linked by making root with larger key child of other. Maintains heap property and order k.

Definition:B0 = single nodeBk = two Bk-1 trees linked: root of one becomes child of root of other root with smaller key is new root

Operations

Overview

Basic operations: insert, merge, find minimum, extract minimum, decrease key, delete. Each preserves heap property.

Amortized Efficiency

Most operations run in O(log n) amortized time. Merge and insert particularly efficient due to binomial tree structure.

Data Integrity

After each operation, heap remains collection of binomial trees with unique orders and heap property.

Merge Operation

Purpose

Combine two binomial heaps into one. Essential for priority queues requiring union functionality.

Algorithm

Merge root lists sorted by degree. Merge trees of equal degree by linking. Repeated until no two trees share same degree.

Complexity

Time complexity: O(log n), where n is total number of nodes. Dominated by merging and linking steps.

Merge(H1, H2): Initialize new root list While roots remain in H1 or H2: Append tree with smaller degree to new list Traverse new list: If two consecutive trees have same degree: Link them into one tree of higher degree Return merged heap

Insertion

Method

Create single-node heap, merge with existing heap. Utilizes merge operation.

Efficiency

Amortized time: O(log n). Actual insertion fast when few tree merges occur.

Effect on Structure

Heap size increments by one. May cause merging of trees if degree conflict arises.

Find Minimum

Strategy

Traverse root list. Minimum key found at one of the roots. No need to traverse entire heap.

Time Complexity

O(log n), where n is number of elements. Number of roots bounded by log n.

Use Cases

Retrieve minimum key for priority queue operations without altering heap structure.

Extract Minimum

Procedure

Locate root with minimum key. Remove this root from root list. Reverse order of its children and merge with remaining heap.

Rationale

Removing min root splits its subtrees into new binomial trees. Re-merging maintains heap properties.

Time Complexity

O(log n) amortized time due to merging and restructuring.

ExtractMin(H): min = root with smallest key Remove min from root list Reverse min's children to form new heap H' H = Merge(H, H') Return min's key

Decrease Key

Objective

Reduce key value of a node to given smaller value. Maintains heap order.

Process

Update node’s key. Bubble up node by swapping with parent while heap property violated.

Complexity

O(log n) worst-case time due to bubbling up along a path to root.

Delete Operation

Method

Decrease key to −∞ (or sentinel minimum). Extract minimum to remove node.

Complexity

Delete operation combines decrease key and extract min, total O(log n) amortized time.

Use Cases

Remove arbitrary node efficiently without full traversal or reconstruction.

Complexity Analysis

Summary Table

Amortized Cost Explanation

Amortized analysis accounts for cascading merges during operations. Ensures average cost per operation remains low.

Applications

Priority Queues

Used when frequent merging of priority queues required. Examples: event-driven simulations, job scheduling.

Graph Algorithms

Widely used in algorithms like Dijkstra’s shortest path and Prim’s minimum spanning tree due to efficient decrease-key.

Dynamic Sets

Efficient for maintaining dynamic ordered sets with fast union and key updates.

References

• Vuillemin, J. "A Data Structure for Manipulating Priority Queues." Communications of the ACM, vol. 21, no. 4, 1978, pp. 309-315.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms. 3rd ed., MIT Press, 2009, pp. 471-483.
• Fredman, M. L., and Tarjan, R. E. "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM, vol. 34, no. 3, 1987, pp. 596-615.
• Sedgewick, R. Algorithms in C++. Addison-Wesley Professional, 1998, pp. 290-295.
• Tarjan, R. E. "Data Structures and Network Algorithms." SIAM, 1983, pp. 194-202.