Praktische Beispiele
Echtweltanwendungen von Priority Queues
1. Task-Scheduling-System (Aufgabenplanungssystem)
#include <queue>
#include <string>
#include <iostream>
struct Task {
int priority;
std::string name;
// Benutzerdefinierter Vergleich für die Priority Queue
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
class TaskScheduler {
private:
std::priority_queue<Task> taskQueue;
public:
void addTask(const std::string& name, int priority) {
taskQueue.push({priority, name});
}
void executeTasks() {
while (!taskQueue.empty()) {
Task currentTask = taskQueue.top();
taskQueue.pop();
std::cout << "Executing task: "
<< currentTask.name
<< " (Priority: "
<< currentTask.priority
<< ")\n";
}
}
};
Ablauf der Task-Scheduling (Aufgabenplanung)
graph TD
A[Add Tasks] --> B{Priority Queue}
B --> C[Highest Priority Task]
C --> D[Execute Task]
D --> E{More Tasks?}
E -->|Yes| C
E -->|No| F[Scheduling Complete]
2. Dijkstra-Algorithmus für kürzeste Wege
#include <queue>
#include <vector>
#include <utility>
class Graph {
private:
std::vector<std::vector<std::pair<int, int>>> adjacencyList;
void dijkstraShortestPath(int start) {
std::priority_queue<
std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>
> pq;
std::vector<int> distances(adjacencyList.size(), INT_MAX);
pq.push({0, start});
distances[start] = 0;
while (!pq.empty()) {
int currentVertex = pq.top().second;
int currentDistance = pq.top().first;
pq.pop();
// Verarbeite benachbarte Knoten
for (auto& neighbor : adjacencyList[currentVertex]) {
int nextVertex = neighbor.first;
int edgeWeight = neighbor.second;
if (currentDistance + edgeWeight < distances[nextVertex]) {
distances[nextVertex] = currentDistance + edgeWeight;
pq.push({distances[nextVertex], nextVertex});
}
}
}
}
};
Vergleich der Anwendungsfälle von Priority Queues
Anwendungsfall |
Hauptvorteil |
Zeitkomplexität |
Task-Scheduling (Aufgabenplanung) |
Zuerst die Aufgaben mit der höchsten Priorität ausführen |
O(log n) |
Kürzester Weg |
Effizienten minimalen Pfad finden |
O((V+E)log V) |
Ereignisgesteuerte Simulation |
Ereignisse nach Priorität verarbeiten |
O(log n) |
3. Ereignisgesteuerte Simulation
#include <queue>
#include <functional>
class EventSimulator {
private:
std::priority_queue<
std::pair<double, std::function<void()>>,
std::vector<std::pair<double, std::function<void()>>>,
std::greater<std::pair<double, std::function<void()>>>
> eventQueue;
public:
void scheduleEvent(double time, std::function<void()> event) {
eventQueue.push({time, event});
}
void runSimulation() {
while (!eventQueue.empty()) {
auto currentEvent = eventQueue.top();
eventQueue.pop();
// Ereignis zur angegebenen Zeit ausführen
currentEvent.second();
}
}
};
Wichtige Erkenntnisse für LabEx-Lerner
- Priority Queues lösen komplexe Sortierungsprobleme.
- Flexible Implementierung in verschiedenen Bereichen.
- Verständnis der Kompromisse bei verschiedenen Anwendungsfällen.
Bei LabEx betonen wir die praktische Anwendung von Datenstrukturen zur Lösung realer Herausforderungen.