## Praktische Beispiele ### Echtweltanwendungen von Priority Queues #### 1. Task-Scheduling-System (Aufgabenplanungssystem) ```cpp #include #include #include 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 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) ```mermaid 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 ```cpp #include #include #include class Graph { private: std::vector>> adjacencyList; void dijkstraShortestPath(int start) { std::priority_queue< std::pair, std::vector>, std::greater> > pq; std::vector 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 ```cpp #include #include class EventSimulator { private: std::priority_queue< std::pair>, std::vector>>, std::greater>> > eventQueue; public: void scheduleEvent(double time, std::function 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 1. Priority Queues lösen komplexe Sortierungsprobleme. 2. Flexible Implementierung in verschiedenen Bereichen. 3. Verständnis der Kompromisse bei verschiedenen Anwendungsfällen. Bei LabEx betonen wir die praktische Anwendung von Datenstrukturen zur Lösung realer Herausforderungen.