Practical Examples
Applications réelles des files de priorité
1. Système de planification de tâches
#include <queue>
#include <string>
#include <iostream>
struct Task {
int priority;
std::string name;
// Custom comparison for 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";
}
}
};
Flux de planification de tâches
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. Algorithme de plus court chemin de Dijkstra
#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();
// Process adjacent vertices
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});
}
}
}
}
};
Comparaison des cas d'utilisation des files de priorité
Cas d'utilisation |
Principal avantage |
Complexité temporelle |
Planification de tâches |
Exécuter les tâches de plus haute priorité en premier |
O(log n) |
Plus court chemin |
Trouver efficacement le chemin minimal |
O((V+E)log V) |
Simulation événementielle |
Traiter les événements par priorité |
O(log n) |
3. Simulation événementielle
#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();
// Execute event at specified time
currentEvent.second();
}
}
};
Points clés pour les apprenants de LabEx
- Les files de priorité résolvent des problèmes d'ordonnancement complexes
- Implémentation flexible dans divers domaines
- Comprendre les compromis dans différents cas d'utilisation
Chez LabEx, nous mettons l'accent sur l'application pratique des structures de données pour résoudre des défis réels.