WikiGalaxy
Priority Queue Implementation
Overview:
Heaps are commonly used to implement priority queues, where elements are processed based on priority rather than order of insertion.
Example:
In a hospital management system, patients are treated based on the severity of their condition, which can be efficiently managed using a priority queue.
import java.util.PriorityQueue;
class HospitalQueue {
public static void main(String args[]) {
PriorityQueue patientQueue = new PriorityQueue<>();
patientQueue.add("Patient A - High");
patientQueue.add("Patient B - Medium");
patientQueue.add("Patient C - Low");
System.out.println(patientQueue);
}
}
Console Output:
[Patient A - High, Patient B - Medium, Patient C - Low]
Heap Sort Algorithm
Overview:
Heap sort is a comparison-based sorting technique based on a binary heap data structure. It is an efficient sorting algorithm with a time complexity of O(n log n).
Example:
Heap sort can be used to sort large datasets efficiently, such as sorting a list of student grades.
import java.util.Arrays;
class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
Console Output:
[5, 6, 7, 11, 12, 13]
Graph Algorithms
Overview:
Heaps are used in graph algorithms like Dijkstra's shortest path algorithm, where the priority queue is used to efficiently get the next vertex with the smallest tentative distance.
Example:
Finding the shortest path in a network routing protocol.
import java.util.*;
class Graph {
private int V;
private LinkedList adj[];
class Node implements Comparable {
int vertex;
int weight;
Node(int v, int w) { vertex = v; weight = w; }
public int compareTo(Node node) { return this.weight - node.weight; }
}
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int u, int v, int w) {
adj[u].add(new Node(v, w));
adj[v].add(new Node(u, w));
}
void dijkstra(int src) {
PriorityQueue pq = new PriorityQueue<>();
int dist[] = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.add(new Node(src, 0));
dist[src] = 0;
while (!pq.isEmpty()) {
int u = pq.poll().vertex;
for (Node node : adj[u]) {
int v = node.vertex;
int weight = node.weight;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v]));
}
}
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " \t\t " + dist[i]);
}
public static void main(String args[]) {
Graph g = new Graph(5);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(0, 4, 3);
g.addEdge(2, 1, 2);
g.addEdge(2, 3, 4);
g.dijkstra(0);
}
}
Console Output:
Vertex Distance from Source 0 0 1 8 2 6 3 5 4 3
Median Maintenance
Overview:
Heaps can be used to maintain the median of a stream of numbers, using two heaps to manage the lower and upper halves of the data.
Example:
Real-time data analysis where you need to frequently update and retrieve the median value.
import java.util.*;
class MedianMaintenance {
PriorityQueue minHeap = new PriorityQueue<>();
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
public void addNumber(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
public static void main(String args[]) {
MedianMaintenance mm = new MedianMaintenance();
mm.addNumber(1);
mm.addNumber(2);
System.out.println(mm.findMedian());
mm.addNumber(3);
System.out.println(mm.findMedian());
}
}
Console Output:
1.5 2.0
Event Simulation
Overview:
Heaps can be used in event-driven simulation systems to manage events based on their scheduled time, ensuring that the next event to occur is processed first.
Example:
Simulating a queue system at a bank, where customer arrivals and service completions are handled in chronological order.
import java.util.*;
class EventSimulation {
static class Event implements Comparable {
int time;
String type;
Event(int t, String tp) { time = t; type = tp; }
public int compareTo(Event e) { return this.time - e.time; }
}
public static void main(String args[]) {
PriorityQueue eventQueue = new PriorityQueue<>();
eventQueue.add(new Event(5, "Arrival"));
eventQueue.add(new Event(2, "Service Completion"));
eventQueue.add(new Event(8, "Arrival"));
while (!eventQueue.isEmpty()) {
Event e = eventQueue.poll();
System.out.println("Event: " + e.type + " at time " + e.time);
}
}
}
Console Output:
Event: Service Completion at time 2 Event: Arrival at time 5 Event: Arrival at time 8
Kth Largest Element in an Array
Overview:
Finding the kth largest element in an array can be efficiently done using a min-heap of size k.
Example:
Identify the third largest salary in a list of employee salaries.
import java.util.*;
class KthLargest {
public int findKthLargest(int[] nums, int k) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public static void main(String args[]) {
KthLargest kl = new KthLargest();
int[] nums = {3, 2, 1, 5, 6, 4};
System.out.println(kl.findKthLargest(nums, 2)); // Output: 5
}
}
Console Output:
5
Merge K Sorted Lists
Overview:
Merging k sorted linked lists into one sorted list can be efficiently achieved using a min-heap.
Example:
Combining multiple sorted datasets into a single sorted dataset for data analysis.
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class MergeKLists {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue queue = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
ListNode head = new ListNode(0);
ListNode current = head;
while (!queue.isEmpty()) {
current.next = queue.poll();
current = current.next;
if (current.next != null) queue.add(current.next);
}
return head.next;
}
public static void main(String args[]) {
MergeKLists mkl = new MergeKLists();
ListNode[] lists = new ListNode[3];
lists[0] = new ListNode(1);
lists[0].next = new ListNode(4);
lists[0].next.next = new ListNode(5);
lists[1] = new ListNode(1);
lists[1].next = new ListNode(3);
lists[1].next.next = new ListNode(4);
lists[2] = new ListNode(2);
lists[2].next = new ListNode(6);
ListNode result = mkl.mergeKLists(lists);
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
}
}
Console Output:
1 1 2 3 4 4 5 6
Top K Frequent Elements
Overview:
Finding the top k frequent elements in an array can be efficiently performed using a heap to maintain the top k elements.
Example:
Determining the most frequently used words in a text document.
import java.util.*;
class TopKFrequent {
public int[] topKFrequent(int[] nums, int k) {
Map countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
PriorityQueue heap = new PriorityQueue<>((n1, n2) -> countMap.get(n1) - countMap.get(n2));
for (int num : countMap.keySet()) {
heap.add(num);
if (heap.size() > k) heap.poll();
}
int[] top = new int[k];
for (int i = k - 1; i >= 0; --i) {
top[i] = heap.poll();
}
return top;
}
public static void main(String args[]) {
TopKFrequent tkf = new TopKFrequent();
int[] nums = {1, 1, 1, 2, 2, 3};
int[] result = tkf.topKFrequent(nums, 2);
System.out.println(Arrays.toString(result));
}
}
Console Output:
[1, 2]
Task Scheduling
Overview:
Heaps can be used in task scheduling algorithms to determine the most optimal order of task execution based on priority and deadlines.
Example:
Scheduling jobs in a manufacturing plant to minimize idle time and meet deadlines.
import java.util.*;
class TaskScheduler {
static class Task implements Comparable {
String name;
int deadline;
Task(String n, int d) { name = n; deadline = d; }
public int compareTo(Task t) { return this.deadline - t.deadline; }
}
public static void main(String args[]) {
PriorityQueue taskQueue = new PriorityQueue<>();
taskQueue.add(new Task("Task 1", 4));
taskQueue.add(new Task("Task 2", 2));
taskQueue.add(new Task("Task 3", 1));
while (!taskQueue.isEmpty()) {
Task t = taskQueue.poll();
System.out.println("Executing: " + t.name + " with deadline " + t.deadline);
}
}
}
Console Output:
Executing: Task 3 with deadline 1 Executing: Task 2 with deadline 2 Executing: Task 1 with deadline 4
