This project implements a Binomial Heap data structure in Java. Binomial heaps support efficient merging, insertion, deletion, and key decrease operations, with each operation having a logarithmic time complexity.
The implementation ensures that key operations maintain a time complexity of O(log n), thanks to the structure's properties and optimal algorithms.
This project was developed as part of the Data Structures course at Tel Aviv University 🎓, in collaboration with a fellow student.
We focused on:
- Writing clean and efficient code
- Implementing well-documented algorithms
- Optimizing runtime performance across various methods 🚀🔍
✅ Insertion (insert(int key, String info)) - Inserts a new key-value pair into the binomial heap.
✅ Delete Minimum (deleteMin()) - Removes the smallest element and restructures the heap.
✅ Search Minimum (findMin()) - Retrieves the minimum element in O(1).
✅ Decrease Key (decreaseKey(HeapItem item, int diff)) - Reduces the key value and ensures heap order.
✅ Delete Any Element (delete(HeapItem item)) - Deletes an arbitrary element efficiently.
✅ Merge (Meld) (meld(BinomialHeap heap2)) - Combines two binomial heaps in O(log n) time.
✅ Heap Size & Tree Count (size(), numTrees()) - Retrieves heap statistics.
| Operation | Method Name | Time Complexity |
|---|---|---|
| Insertion | insert(int key, String info) |
O(log n) |
| Find Minimum | findMin() |
O(1) |
| Delete Minimum | deleteMin() |
O(log n) |
| Decrease Key | decreaseKey(HeapItem item, int diff) |
O(log n) |
| Delete Any Item | delete(HeapItem item) |
O(log n) |
| Merge (Meld) | meld(BinomialHeap heap2) |
O(log n) |
| Get Heap Size | size() |
O(1) |
| Get Number of Trees | numTrees() |
O(1) |
| Check if Empty | empty() |
O(1) |
public class Main {
public static void main(String[] args) {
BinomialHeap heap = new BinomialHeap();
// Insert elements
heap.insert(10, "Ten");
heap.insert(20, "Twenty");
heap.insert(5, "Five");
// Find minimum element
System.out.println("Min: " + heap.findMin().getKey());
// Delete minimum element
heap.deleteMin();
System.out.println("New Min: " + heap.findMin().getKey());
// Decrease key
HeapItem item = heap.insert(15, "Fifteen");
heap.decreaseKey(item, 5);
System.out.println("Min after decrease key: " + heap.findMin().getKey());
// Delete an item
heap.delete(item);
}
}