इस ट्यूटोरियल में, आप सीखेंगे कि प्राथमिकता कतार क्या है। इसके अलावा, आप पायथन, जावा, सी और सी ++ में इसके कार्यान्वयन के बारे में जानेंगे।
एक प्राथमिकता कतार एक विशेष प्रकार की कतार है जिसमें प्रत्येक तत्व एक प्राथमिकता के साथ जुड़ा हुआ है और उसकी प्राथमिकता के अनुसार सेवा की जाती है। यदि समान प्राथमिकता वाले तत्व होते हैं, तो उन्हें कतार में उनके आदेश के अनुसार परोसा जाता है।
आमतौर पर, तत्व के मूल्य को प्राथमिकता देने के लिए माना जाता है।
उदाहरण के लिए, उच्चतम मूल्य वाला तत्व सर्वोच्च प्राथमिकता वाला तत्व माना जाता है। हालांकि, अन्य मामलों में, हम उच्चतम मूल्य वाले तत्व के रूप में सबसे कम मूल्य वाले तत्व को मान सकते हैं। अन्य मामलों में, हम अपनी आवश्यकताओं के अनुसार प्राथमिकताएँ निर्धारित कर सकते हैं।
उच्चतम प्राथमिकता तत्व निकालना
प्राथमिकता कतार और सामान्य कतार के बीच अंतर
एक कतार में, पहला-पहला नियम लागू किया जाता है, जबकि एक प्राथमिकता कतार में, प्राथमिकता के आधार पर मान हटा दिए जाते हैं । सर्वोच्च प्राथमिकता वाला तत्व पहले हटा दिया जाता है।
प्राथमिकता कतार का कार्यान्वयन
प्राथमिकता कतार एक सरणी, एक लिंक की गई सूची, एक ढेर डेटा संरचना, या एक द्विआधारी खोज पेड़ का उपयोग करके लागू की जा सकती है। इन डेटा संरचनाओं के बीच, ढेर डेटा संरचना प्राथमिकता कतार का एक कुशल कार्यान्वयन प्रदान करता है।
इसलिए, हम इस ट्यूटोरियल में प्राथमिकता कतार को लागू करने के लिए ढेर डेटा संरचना का उपयोग करेंगे। एक अधिकतम-ढेर लागू होता है, निम्नलिखित कार्यों में है। यदि आप इसके बारे में अधिक जानना चाहते हैं, तो कृपया अधिकतम-ढेर और मध्य-ढेर पर जाएँ।
प्राथमिकता कतार के विभिन्न कार्यान्वयनों का तुलनात्मक विश्लेषण नीचे दिया गया है।
| संचालन | झांकना | सम्मिलित करें | हटा दें |
|---|---|---|---|
| लिंक्ड सूची | O(1) | O(n) | O(1) |
| बाइनरी हीप | O(1) | O(log n) | O(log n) |
| बाइनरी सर्च ट्री | O(1) | O(log n) | O(log n) |
प्राथमिकता कतार संचालन
एक प्राथमिकता कतार के बुनियादी संचालन तत्वों को सम्मिलित करना, हटाना और हटाना है।
प्राथमिकता कतार का अध्ययन करने से पहले, बाइनरी हीप की बेहतर समझ के लिए कृपया ढेर डेटा संरचना को देखें क्योंकि इसका उपयोग इस लेख में प्राथमिकता कतार को लागू करने के लिए किया जाता है।
1. प्राथमिकता कतार में एक तत्व सम्मिलित करना
एक तत्व को प्राथमिकता कतार (अधिकतम-ढेर) में सम्मिलित करना निम्नलिखित चरणों द्वारा किया जाता है।
- पेड़ के अंत में नया तत्व डालें।
कतार के अंत में एक तत्व डालें - पेड़ को ढेर करो।
सम्मिलन के बाद ढेर करें
तत्व को प्राथमिकता कतार में डालने के लिए एल्गोरिथम (अधिकतम-ढेर)
यदि कोई नोड नहीं है, तो एक नया नोड बनाएं। और (एक नोड पहले से मौजूद है) अंत में नया नोड डालें (अंतिम नोड बाएं से दाएं।) सरणी को हटा दें।
मिन हीप के लिए, उपरोक्त एल्गोरिथ्म को संशोधित किया गया है ताकि parentNodeहमेशा की तुलना में छोटा हो newNode।
2. प्राथमिकता कतार से एक तत्व हटाना
एक प्राथमिकता कतार से एक तत्व को हटाना (अधिकतम-ढेर) निम्नानुसार किया जाता है:
- हटाए जाने वाले तत्व का चयन करें।
हटाए जाने वाले तत्व का चयन करें - अंतिम तत्व के साथ इसे स्वैप करें।
अंतिम पत्ती नोड तत्व के साथ स्वैप करें - अंतिम तत्व निकालें।
अंतिम तत्व पत्ती निकालें - पेड़ को ढेर करो।
प्राथमिकता कतार को छोटा करें
प्राथमिकता कतार में एक तत्व को हटाने के लिए एल्गोरिथम (अधिकतम-ढेर)
अगर नोडटबबलेट किया गया है तो लीफएनोड हटा दें नोड को हटा दें स्वैप नोड नोड को हटा दें
मिन हीप के लिए, उपरोक्त एल्गोरिथ्म को संशोधित किया गया है ताकि दोनों की childNodesतुलना में छोटा हो currentNode।
3. प्राथमिकता कतार से झांकना (अधिकतम / मिनट लगाएं)
पीक ऑपरेशन नोड को हटाए बिना अधिकतम हीप से अधिकतम तत्व या न्यूनतम हीप से न्यूनतम तत्व देता है।
मैक्स हीप और मिन हीप दोनों के लिए
रूटकोड वापस करें
4. प्राथमिकता कतार से एक्सट्रैक्ट-मैक्स / मिन
एक्सट-मैक्स नोड को अधिकतम हीप से हटाने के बाद अधिकतम मान के साथ लौटाता है जबकि एक्स्ट-मिन नोड को न्यूनतम मूल्य से कम करने के बाद वापस करता है।
पायथन, जावा, सी और सी ++ में प्राथमिकता कतार कार्यान्वयन
पायथन जावा सी सी ++ # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
// Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )
// Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )
प्राथमिकता कतार अनुप्रयोग
एक प्राथमिकता कतार के कुछ अनुप्रयोग हैं:
- दीजकस्ट्रा का एल्गोरिदम
- स्टैक को लागू करने के लिए
- एक ऑपरेटिंग सिस्टम में लोड बैलेंसिंग और इंटरप्ट हैंडलिंग के लिए
- हफ़मैन कोड में डेटा संपीड़न के लिए
