Creating a priority queue in Java can be efficiently achieved using various data structures such as binary heaps, Fibonacci heaps, and binomial heaps. Each of these structures offers different advantages in terms of insertion, deletion, and decrease-key operations, which are crucial for priority queue operations.
Below, we’ll outline implementations for each and discuss why Fibonacci Heap is often considered superior to Binary Heap for certain applications.
1. Binary Heap
A binary heap is a complete binary tree where each node is smaller than its children for a min-heap or larger for a max-heap. It’s efficient for both insertion and removal operations.
Binary heaps are particularly suited for priority queue implementations because they can ensure that the queue’s “peek” operation (finding the minimum or maximum) is always O(1), while insertion and removal operations are logarithmic (O(log n)) in complexity.
Implementing a Priority Queue with Binary Heap
Here’s a simple Java class that implements a min-priority queue using a binary heap:
import java.util.*;
public class BinaryHeapPriorityQueue{
private List<Integer> heap;
public BinaryHeapPriorityQueue(){
heap = new ArrayList<>();
}
public void insert(int element){
heap.add(element);
int currentIndex = heap.size() - 1;
while(currentIndex > 0){
int parentIndex = (currentIndex -1) /2;
if(heap.get(currentIndex) < heap.get(parentIndex)){
Collections.swap(heap, currentIndex, parentIndex);
currentIndex = parentIndex;
}else{
break;
}
}
}
public int remove(){
if(heap.size() == 0)
throw new NoSuchElementException("Heap is empty");
int removeItem = heap.get(0);
heap.set(0, heap.get(heap.size()-1));
heap.remove(heap.get(heap.size() -1));
heapify(0);
return removeItem;
}
private void heapify(int index){
int leftChildIndex = 2 *index +1;
int rightChildIndex = 2 * index +2;
int smallestIndex = index;
if(leftChildIndex < heap.size() && heap.get(leftChildIndex) < heap.get(smallestIndex)){
smallestIndex = leftChildIndex;
}
if(rightChildIndex < heap.size() && heap.get(rightChildIndex) < heap.get(smallestIndex)){
smallestIndex = rightChildIndex;
}
if(index != smallestIndex){
Collections.swap(heap, index, smallestIndex);
heapify(smallestIndex);
}
}
public static void main(String[] args) {
BinaryHeapPriorityQueue binaryHeapPriorityQueue = new BinaryHeapPriorityQueue();
binaryHeapPriorityQueue.insert(-12);
binaryHeapPriorityQueue.insert(12);
binaryHeapPriorityQueue.insert(13);
binaryHeapPriorityQueue.insert(1);
binaryHeapPriorityQueue.insert(2);
System.out.println(binaryHeapPriorityQueue.remove());
System.out.println(binaryHeapPriorityQueue.remove());
}
}
2. Fibonacci Heap
The Fibonacci Heap is a more complex structure. It offers better average-case performance for some operations, particularly for decrease-key and merge operations, making it ideal for algorithms like Dijkstra’s shortest path.
Implementing a full Fibonacci Heap in Java is quite involved due to its complexity, especially in handling all operations efficiently. Here’s a simplified version to illustrate its structure:
public class FibonacciHeapNode {
int key;
FibonacciHeapNode child;
FibonacciHeapNode left;
FibonacciHeapNode right;
int degree;
boolean mark;
public FibonacciHeapNode(int key) {
this.key = key;
this.degree = 0;
this.mark = false;
this.left = this;
this.right = this;
}
}
public class FibonacciHeap {
private FibonacciHeapNode min;
private int n;
public FibonacciHeap() {
min = null;
n = 0;
}
public void insert(int key) {
FibonacciHeapNode node = new FibonacciHeapNode(key);
if (min != null) {
node.left = min;
node.right = min.right;
min.right = node;
node.right.left = node;
if (key < min.key) {
min = node;
}
} else {
min = node;
}
n++;
}
// Additional methods for decreaseKey, delete, etc., are required for a complete implementation
}
