Med Java

User Tools

Site Tools

Trace:
java:algorithms:priority-queue

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
java:algorithms:priority-queue [2025/03/16 11:50] – odeftajava:algorithms:priority-queue [2025/03/16 11:51] (current) – odefta
Line 8: Line 8:
  
 Dijkstra: Always selects the node with minimum distance for exploration, guaranteeing optimal path finding. Dijkstra: Always selects the node with minimum distance for exploration, guaranteeing optimal path finding.
 +
 A*: Expands nodes in order of estimated total cost (f = g + h), prioritizing promising paths. A*: Expands nodes in order of estimated total cost (f = g + h), prioritizing promising paths.
 +
 Prim: Always chooses the edge with minimum cost to build the minimum spanning tree. Prim: Always chooses the edge with minimum cost to build the minimum spanning tree.
  
Line 14: Line 16:
  
 CPU Scheduling: Organizes processes by priority, ensuring execution of the most important tasks. CPU Scheduling: Organizes processes by priority, ensuring execution of the most important tasks.
 +
 Event Simulations: Processes events in chronological order or by importance. Event Simulations: Processes events in chronological order or by importance.
 +
 Load Balancing: Distributes tasks based on priority and availability. Load Balancing: Distributes tasks based on priority and availability.
  
Line 24: Line 28:
  
 Top K elements: Efficiently maintains the largest/smallest k elements from a collection without sorting the entire set. Top K elements: Efficiently maintains the largest/smallest k elements from a collection without sorting the entire set.
 +
 Median of a stream: Keeps two heaps to calculate the median in real-time. Median of a stream: Keeps two heaps to calculate the median in real-time.
 +
 K-Nearest Neighbors: Identifies the closest k neighbors in a multidimensional space. K-Nearest Neighbors: Identifies the closest k neighbors in a multidimensional space.
  
Line 30: Line 36:
  
 Interval Scheduling: Selects activities that finish earliest. Interval Scheduling: Selects activities that finish earliest.
 +
 Huffman Coding: Builds optimal encoding trees. Huffman Coding: Builds optimal encoding trees.
 +
 Minimum Spanning Tree: Constructs minimum cost trees. Minimum Spanning Tree: Constructs minimum cost trees.
  
Line 36: Line 44:
  
 Streaming Analytics: Identifies trends and anomalies in real-time. Streaming Analytics: Identifies trends and anomalies in real-time.
 +
 Sliding Window: Maintains the most relevant k elements in a sliding window. Sliding Window: Maintains the most relevant k elements in a sliding window.
 +
 Rate Limiting: Controls event frequency in distributed systems. Rate Limiting: Controls event frequency in distributed systems.
  
Line 42: Line 52:
  
 Branch and Bound: Explores the most promising partial solutions first. Branch and Bound: Explores the most promising partial solutions first.
 +
 Knapsack Problem: Selects items with maximum value for a limited capacity. Knapsack Problem: Selects items with maximum value for a limited capacity.
 +
 Job Sequencing: Organizes tasks to maximize profit or minimize delays. Job Sequencing: Organizes tasks to maximize profit or minimize delays.
  
Line 48: Line 60:
  
 Kruskal with Union-Find: Builds minimum spanning trees. Kruskal with Union-Find: Builds minimum spanning trees.
 +
 Johnson's Algorithm: Calculates shortest paths between all pairs of nodes. Johnson's Algorithm: Calculates shortest paths between all pairs of nodes.
 +
 Network Flow: Optimizes flow in a network with capacities. Network Flow: Optimizes flow in a network with capacities.
  
Line 54: Line 68:
  
 Merge Overlapping Intervals: Efficiently combines overlapping intervals. Merge Overlapping Intervals: Efficiently combines overlapping intervals.
 +
 Meeting Rooms: Determines the minimum number of rooms needed for scheduling meetings. Meeting Rooms: Determines the minimum number of rooms needed for scheduling meetings.
 +
 Skyline Problem: Calculates the outline formed by buildings. Skyline Problem: Calculates the outline formed by buildings.
  
Line 60: Line 76:
  
 Fibonacci Heaps: Implements decrease-key operations in amortized O(1) time. Fibonacci Heaps: Implements decrease-key operations in amortized O(1) time.
 +
 Treap: Combines binary search trees with heaps for efficient operations. Treap: Combines binary search trees with heaps for efficient operations.
 +
 Segment Trees: Supports range queries and updates. Segment Trees: Supports range queries and updates.
  
Line 66: Line 84:
  
 Quick access to the extreme element (O(1)) Quick access to the extreme element (O(1))
 +
 Efficient insertion and extraction (O(log n)) Efficient insertion and extraction (O(log n))
 +
 Memory efficient compared to maintaining a sorted list Memory efficient compared to maintaining a sorted list
 +
 Flexibility through custom comparators Flexibility through custom comparators
 +
 Simple implementation using binary heaps Simple implementation using binary heaps
  
 ===== Java Implementation ===== ===== Java Implementation =====
  
-// Max-heap (maximum element at top) PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());+<code java> 
 +// Min-heap (minimum element at top) 
 +PriorityQueue<Integer> minHeap = new PriorityQueue<>(); 
 + 
 +// Max-heap (maximum element at top) 
 +PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
  
-// With custom comparator PriorityQueue taskQueue = new PriorityQueue<>((t1, t2) -> t1.getPriority() - t2.getPriority());+// With custom comparator 
 +PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> 
 +t1.getPriority() - t2.getPriority());
  
-// Basic operations minHeap.offer(element); // Add element int top = minHeap.peek(); // Access top int removed = minHeap.poll(); // Extract top+// Basic operations 
 +minHeap.offer(element);  // Add element 
 +int top = minHeap.peek();  // Access top 
 +int removed = minHeap.poll();  // Extract top 
 +</code>
  
 ===== Complexity ===== ===== Complexity =====
  
-^ Operation ^ Complexity ^ | peek() | O(1) | | offer() / add() | O(log n) | | poll() / remove() | O(log n) | | contains() | O(n) | | remove(Object) | O(n) |+^  Operation  ^  Complexity  ^ 
 +|  peek()  |  O(1)  | 
 +|  offer() / add()  |  O(log n)  | 
 +|  poll() / remove()  |  O(log n)  | 
 +|  contains()  |  O(n)  | 
 +|  remove(Object)  |  O(n)  |
  
 ===== Conclusions ===== ===== Conclusions =====
  
 Priority Queue is a fundamental data structure in algorithms, offering an excellent balance between efficiency and simplicity. Its appropriate use can significantly improve the performance of algorithms that require repeated access to extreme elements from a dynamic collection. Priority Queue is a fundamental data structure in algorithms, offering an excellent balance between efficiency and simplicity. Its appropriate use can significantly improve the performance of algorithms that require repeated access to extreme elements from a dynamic collection.
java/algorithms/priority-queue.1742118622.txt.gz · Last modified: 2025/03/16 11:50 by odefta