एक प्राथमिकता कतार एक मौलिक डेटा संरचना है जो प्रत्येक तत्व को प्राथमिकता प्रदान करके एक मानक कतार की कार्यक्षमता का विस्तार करती है। एक FIFO (First-In, First-Out) कतार के विपरीत जहाँ तत्वों को उनके आने के क्रम में संसाधित किया जाता है, एक प्राथमिकता कतार अपनी प्राथमिकता के आधार पर तत्वों को डीक्यू (हटाता) करती है। उच्चतम-प्राथमिकता वाला तत्व हमेशा पहले संसाधित किया जाता है। यह प्राथमिकता संख्यात्मक मान (सबसे छोटा या सबसे बड़ा), या किसी भी कस्टम तुलना मानदंड पर आधारित हो सकती है।
प्राथमिकता कतारें कई एल्गोरिदम और अनुप्रयोगों में अमूल्य हैं जहाँ महत्व के आधार पर कार्यों या घटनाओं का कुशल प्रबंधन महत्वपूर्ण है। उदाहरणों में शामिल हैं:
- सबसे छोटा कार्य पहले (SJF) शेड्यूलिंग: ऑपरेटिंग सिस्टम में, उनके अनुमानित निष्पादन समय के आधार पर प्रक्रियाओं को कुशलतापूर्वक शेड्यूल करना।
- बेस्ट-फर्स्ट सर्च एल्गोरिदम (A*, Dijkstra’s): लक्ष्य से उनकी अनुमानित दूरी के आधार पर नोड्स को प्राथमिकता देकर ग्राफ़ में इष्टतम पथ खोजना।
- घटना सिमुलेशन: असतत घटना सिमुलेशन में घटनाओं का प्रबंधन करना, यह सुनिश्चित करना कि सबसे जरूरी घटनाओं को पहले संभाला जाए।
- हीप सॉर्ट: एक सॉर्टिंग एल्गोरिथम जो कुशल सॉर्टिंग के लिए एक हीप (प्राथमिकता कतार के एक विशेष प्रकार) के गुणों का लाभ उठाता है।
- हफ़मैन कोडिंग: उनकी आवृत्ति के आधार पर प्रतीकों को प्राथमिकता देकर कुशल संपीड़न एल्गोरिदम का निर्माण करना।
C# में प्राथमिकता कतारों को लागू करना
C# प्राथमिकता कतार को लागू करने के कई तरीके प्रदान करता है। आइए दो सामान्य तरीकों का पता लगाएं:
1. SortedSet का उपयोग करना
बिल्ट-इन SortedSet क्लास प्राथमिकता कतार को लागू करने का एक सुविधाजनक तरीका प्रदान करता है। SortedSet स्वचालित रूप से अपने तत्वों को क्रमबद्ध क्रम में बनाए रखता है, प्राथमिकता को सरल करता है। यह विशेष रूप से उपयोगी है जब प्राथमिकता तत्वों के प्राकृतिक क्रम (जैसे, पूर्णांक) द्वारा स्पष्ट रूप से निर्धारित की जाती है।
using System;
using System.Collections.Generic;
public class PriorityQueueSortedSet<T> where T : IComparable<T>
{
private SortedSet<T> _elements = new SortedSet<T>();
public void Enqueue(T item) => _elements.Add(item);
public T Dequeue()
{
if (_elements.Count == 0)
{
throw new InvalidOperationException("Priority queue is empty.");
}
T item = _elements.Min;
_elements.Remove(item);
return item;
}
public bool IsEmpty() => _elements.Count == 0;
public int Count => _elements.Count;
}
यह कार्यान्वयन सरल है, लेकिन इसका प्रदर्शन अंतर्निहित SortedSet द्वारा सीमित है, जो एनक्यू और डीक्यू ऑपरेशन के लिए O(log n) जटिलता प्रदान करता है। विशेष रूप से बड़े डेटासेट के लिए मेमोरी उपयोग भी अपेक्षाकृत अधिक हो सकता है।
2. मिन-हीप को लागू करना
बेहतर प्रदर्शन के लिए, विशेष रूप से बड़े डेटासेट के साथ, एक कस्टम मिन-हीप कार्यान्वयन महत्वपूर्ण लाभ प्रदान करता है। एक मिन-हीप एक बाइनरी ट्री संरचना है जो हमेशा यह सुनिश्चित करती है कि सबसे छोटा तत्व रूट पर हो, जिससे एनक्यू और डीक्यू ऑपरेशन दोनों के लिए O(log n) जटिलता मिलती है। SortedSet की तुलना में लागू करने में अधिक जटिल होने पर भी, एक मिन-हीप बेहतर प्रदर्शन और मेमोरी प्रबंधन पर बारीक नियंत्रण प्रदान करता है।
(इस लेख के दायरे से परे एक विस्तृत मिन-हीप कार्यान्वयन है, लेकिन कई संसाधन ऑनलाइन उपलब्ध हैं।)
कार्यान्वयन की तुलना
| सुविधा | SortedSet |
मिन-हीप |
|---|---|---|
| उपयोग में आसानी | आसान | अधिक कठिन |
| एनक्यू/डीक्यू प्रदर्शन | O(log n) | O(log n) |
| मेमोरी उपयोग | संभावित रूप से उच्च | संभावित रूप से कम |
| लचीलापन | कम | अधिक |
सही कार्यान्वयन चुनना
SortedSet और एक कस्टम मिन-हीप के बीच इष्टतम विकल्प आपकी विशिष्ट आवश्यकताओं पर निर्भर करता है। SortedSet सरल अनुप्रयोगों के लिए आदर्श है जहाँ कार्यान्वयन में आसानी अत्यधिक प्रदर्शन की आवश्यकता से अधिक है। प्रदर्शन-महत्वपूर्ण अनुप्रयोगों या बड़े डेटासेट के लिए, एक कस्टम मिन-हीप कार्यान्वयन गति और मेमोरी दक्षता में पर्याप्त लाभ प्रदान करता है।