what is heap data structure java
यह ट्यूटोरियल बताता है कि जावा हीप डेटा स्ट्रक्चर और संबंधित अवधारणाएं जैसे कि मिन हीप, मैक्स हीप, हीप सॉर्ट, स्टैक बनाम हीप जैसे उदाहरण हैं:
एक ढेर जावा में एक विशेष डेटा संरचना है। एक ढेर एक पेड़-आधारित डेटा संरचना है और इसे पूर्ण बाइनरी ट्री के रूप में वर्गीकृत किया जा सकता है। ढेर के सभी नोड्स को एक विशिष्ट क्रम में व्यवस्थित किया जाता है।
=> सभी के लिए जावा प्रशिक्षण श्रृंखला देखने के लिए यहां जाएं
आप क्या सीखेंगे:
जावा में ढेर डेटा संरचना
ढेर डेटा संरचना में, रूट नोड की अपने बच्चों के साथ तुलना की जाती है और आदेश के अनुसार व्यवस्थित किया जाता है। इसलिए यदि कोई मूल नोड है और b उसका बच्चा है, तो संपत्ति, कुंजी (ए)> = कुंजी (बी) एक अधिकतम ढेर उत्पन्न करेगा।
जड़ और बच्चे के नोड के बीच उपरोक्त संबंध को 'हीप संपत्ति' कहा जाता है।
माता-पिता-बच्चे के नोड्स के आदेश के आधार पर, ढेर आमतौर पर दो प्रकार के होते हैं:
(1) मैक्स-हीप :मैक्स-हीप में रूट नोड कुंजी हीप की सभी चाबियों में से सबसे बड़ी है। यह सुनिश्चित किया जाना चाहिए कि एक ही संपत्ति ढेर में सभी उपप्रकारों के लिए सच है।
नीचे दिए गए चित्र में एक नमूना अधिकतम ढेर दिखाया गया है। ध्यान दें कि रूट नोड अपने बच्चों की तुलना में अधिक है।
# 2) मिन-हीप :मिन-हीप के मामले में, रूट नोड कुंजी हीप में मौजूद अन्य सभी चाबियों में सबसे छोटी या न्यूनतम है। जैसा कि मैक्स हीप में है, यह संपत्ति अन्य सभी उपप्रकारों के ढेर में पुनरावर्ती रूप से सही होनी चाहिए।
एक उदाहरण, मिन-हीप ट्री का, नीचे दिखाया गया है। जैसा कि हम देख सकते हैं, रूट कुंजी ढेर में अन्य सभी चाबियों में सबसे छोटी है।
निम्न क्षेत्रों में एक ढेर डेटा संरचना का उपयोग किया जा सकता है:
- हीप्स का इस्तेमाल प्रायः प्रायोरिटी क्यूज़ को लागू करने में किया जाता है।
- विशेष रूप से न्यूनतम-ढेर का उपयोग एक ग्राफ में कोने के बीच सबसे छोटे रास्तों को निर्धारित करने के लिए किया जा सकता है।
जैसा कि पहले ही उल्लेख किया गया है, ढेर डेटा संरचना एक पूर्ण बाइनरी ट्री है जो रूट और बच्चों के लिए ढेर संपत्ति को संतुष्ट करता है। इस ढेर को भी कहा जाता है बाइनरी हीप ।
बाइनरी हीप
एक बाइनरी हीप नीचे के गुणों को पूरा करता है:
- एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है। एक पूर्ण बाइनरी ट्री में, अंतिम स्तर को छोड़कर सभी स्तर पूरी तरह से भरे हुए हैं। अंतिम स्तर पर, कुंजियाँ यथासंभव शेष हैं।
- यह ढेर संपत्ति को संतुष्ट करता है। बाइनरी हीप अधिकतम या न्यूनतम-हीप हो सकता है जो ढेर की संपत्ति पर निर्भर करता है।
एक बाइनरी हीप को आम तौर पर एक ऐरे के रूप में दर्शाया जाता है। जैसा कि यह एक पूर्ण बाइनरी ट्री है, इसे आसानी से एक सरणी के रूप में दर्शाया जा सकता है। इस प्रकार बाइनरी हीप के एक सरणी निरूपण में, मूल तत्व A [0] होगा जहां A बाइनरी हीप का प्रतिनिधित्व करने के लिए उपयोग किया जाने वाला सरणी है।
तो सामान्य तौर पर किसी भी i के लिएवेंबाइनरी हीप सरणी प्रतिनिधित्व, ए [i] में नोड, हम नीचे दिखाए गए अनुसार अन्य नोड्स के सूचकांकों का प्रतिनिधित्व कर सकते हैं।
ए [(आई -1) / 2] | मूल नोड का प्रतिनिधित्व करता है |
---|---|
पहुंच और तेज है। | ढेर से धीमी। |
A [(2 * i) +1] | बाएं बच्चे के नोड का प्रतिनिधित्व करता है |
ए [(2 * i) +2] | सही बच्चे के नोड का प्रतिनिधित्व करता है |
निम्नलिखित बाइनरी हीप पर विचार करें:
उपरोक्त न्यूनतम बाइनरी हीप का सरणी प्रतिनिधित्व इस प्रकार है:
जैसा कि ऊपर दिखाया गया है, ढेर का पता लगाया गया है स्तर का आदेश यानी तत्वों को प्रत्येक स्तर पर बाएं से दाएं तक का पता लगाया जाता है। जब एक स्तर पर तत्व समाप्त हो जाते हैं, तो हम अगले स्तर पर चले जाते हैं।
अगला, हम बाइनरी हीप को जावा में लागू करेंगे।
नीचे दिया गया प्रोग्राम जावा में बाइनरी हीप को प्रदर्शित करता है।
import java.util.*; class BinaryHeap { private static final int d= 2; private int[] heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int[ capacity+1]; Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap[heapSize++] = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap[x]; heap[x] = heap[heapSize -1]; heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap[i]; while(i>0 && temp > heap[parent(i)]){ heap[i] = heap[parent(i)]; i = parent(i); } heap[i] = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap[i]; while(kthChild(i, 1) heap[rightChild]?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i आउटपुट:
nHeap = 7 4 6 1 3 2 5
जावा में मिन हीप
जावा में एक मिन-हीप एक पूर्ण बाइनरी ट्री है। मिन-हीप में, रूट नोड ढेर में अन्य सभी नोड्स की तुलना में छोटा है। सामान्य तौर पर, प्रत्येक आंतरिक नोड का मुख्य मूल्य उसके बच्चे के नोड्स की तुलना में छोटा या बराबर होता है।
जहां तक मिन-हीप के सरणी प्रतिनिधित्व का संबंध है, यदि कोई नोड स्थिति array i ’पर संग्रहीत किया जाता है, तो उसके बाएं बच्चे के नोड को 2i + 1 की स्थिति में संग्रहीत किया जाता है और फिर दाईं ओर का बच्चा नोड 2i + 2 की स्थिति में होता है। स्थिति (i-1) / 2 अपने मूल नोड को लौटाती है।
नीचे सूचीबद्ध किए गए विभिन्न ऑपरेशन मिन-हीप द्वारा समर्थित हैं।
# 1) सम्मिलित करें (): प्रारंभ में, पेड़ के अंत में एक नई कुंजी जोड़ी जाती है। यदि कुंजी अपने मूल नोड से बड़ा है, तो ढेर संपत्ति को बनाए रखा जाता है। अन्यथा, हमें ढेर संपत्ति को पूरा करने के लिए कुंजी को ऊपर की ओर झुकाना होगा। मिनट के ढेर में सम्मिलन का संचालन ओ (लॉग एन) समय लेता है।
# 2) एक्सट्रीमिन (): यह ऑपरेशन हीप से न्यूनतम तत्व को निकालता है। ध्यान दें कि ढेर से रूट तत्व (न्यूनतम तत्व) को हटाने के बाद ढेर संपत्ति को बनाए रखा जाना चाहिए। यह पूरा ऑपरेशन O (लोगन) लेता है।
# 3) getMin (): getMin () ढेर का मूल रिटर्न देता है जो न्यूनतम तत्व भी है। यह ऑपरेशन ओ (1) समय में किया जाता है।
नीचे दिए गए मिन-ढेर के लिए एक उदाहरण पेड़ है।
उपरोक्त आरेख में एक मिन-हीप ट्री दिखाया गया है। हम देखते हैं कि पेड़ की जड़ पेड़ में न्यूनतम तत्व है। जैसा कि मूल स्थान 0 पर है, इसके बाएं बच्चे को 2 * 0 + 1 = 1 पर रखा गया है और दाएं बच्चे को 2 * 0 + 1 = 2 पर रखा गया है।
मिन हीप एल्गोरिदम
नीचे दिया गया है मिन-हीप बनाने के लिए एल्गोरिथ्म।
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A[ ] , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A[left] < A[ i ] ) smallest = left; else smallest = i; if(right <= N and A[right] < A[smallest] ) smallest = right; if(smallest != i) { swap A[ i ] and A[ smallest ]); call min_heapify (A, smallest,N); } }
जावा में न्यूनतम हीप कार्यान्वयन
हम सरणी या प्राथमिकता कतारों का उपयोग करके न्यूनतम-ढेर को लागू कर सकते हैं। प्राथमिकता वाले कतारों का उपयोग करते हुए न्यूनतम-हीप को लागू करना एक प्राथमिक प्राथमिकता है क्योंकि प्राथमिकता-कतार को न्यूनतम-ढेर के रूप में लागू किया जाता है।
निम्न जावा प्रोग्राम Arrays का उपयोग करके मिन-हीप को लागू करता है। यहां हम हीप के लिए ऐरे प्रतिनिधित्व का उपयोग करते हैं और फिर हीप में जोड़े गए प्रत्येक तत्व की हीप संपत्ति को बनाए रखने के लिए हाइपर फंक्शन लागू करते हैं। अंत में, हम ढेर प्रदर्शित करते हैं।
class Min_Heap { private int[] HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int[this.maxsize + 1]; HeapArray[0] = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray[leftChild(pos)] || HeapArray[pos] > HeapArray[rightChild(pos)]) { // swap with left child and then heapify the left child if (HeapArray[leftChild(pos)] = maxsize) { return; } HeapArray[++size] = element; int current = size; while (HeapArray[current] = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray[FRONT]; HeapArray[FRONT] = HeapArray[size--]; minHeapify(FRONT); return popped; } } class Main{ public static void main(String[] arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } }
आउटपुट:
मैक्स हीप इन जावा
एक अधिकतम ढेर भी एक पूर्ण बाइनरी ट्री है। एक अधिकतम ढेर में, रूट नोड बच्चे के नोड्स से अधिक या बराबर है। सामान्य तौर पर, अधिकतम ढेर में किसी भी आंतरिक नोड का मूल्य उसके बच्चे के नोड्स से अधिक या उसके बराबर होता है।
जबकि अधिकतम हीप को एक सरणी में मैप किया जाता है, यदि कोई नोड स्थिति, i ’पर संग्रहीत किया जाता है, तो उसके बाएं बच्चे को 2i +1 पर और दाएं बच्चे को 2i + 2 में संग्रहीत किया जाता है।
विशिष्ट मैक्स-हीप नीचे दिखाए गए अनुसार होगा:
उपरोक्त आरेख में, हम देखते हैं कि रूट नोड ढेर में सबसे बड़ा है और इसके बच्चे नोड्स में रूट नोड की तुलना में छोटे मूल्य हैं।
न्यूनतम-ढेर के समान, अधिकतम ढेर को एक सरणी के रूप में भी दर्शाया जा सकता है।
इसलिए यदि A एक ऐसा सरणी है जो मैक्स हीप का प्रतिनिधित्व करता है तो A [0] रूट नोड है। इसी तरह, यदि ए [i] अधिकतम ढेर में कोई नोड है, तो निम्नलिखित अन्य आसन्न नोड्स हैं जिन्हें एक सरणी का उपयोग करके दर्शाया जा सकता है।
- A [(i-1) / 2] A [i] के मूल नोड का प्रतिनिधित्व करता है।
- A [(2i +1)] A [i] के बाएं बच्चे के नोड का प्रतिनिधित्व करता है।
- A [2i + 2] A [i] का सही चाइल्ड नोड लौटाता है।
मैक्स हीप पर जो ऑपरेशन किए जा सकते हैं, वे नीचे दिए गए हैं।
# 1) डालें: सम्मिलित करें ऑपरेशन अधिकतम ढेर पेड़ में एक नया मूल्य सम्मिलित करता है। इसे पेड़ के अंत में डाला जाता है। यदि नई कुंजी (मान) उसके मूल नोड से छोटी है, तो ढेर संपत्ति को बनाए रखा जाता है। अन्यथा, पेड़ को ढेर संपत्ति को बनाए रखने के लिए ढेर करने की आवश्यकता है।
मुफ्त youtube से mp4 वीडियो डाउनलोडर
सम्मिलित ऑपरेशन की समय जटिलता हे (लॉग एन) है।
# 2) ExtractMax: ऑपरेशन एक्सट्रैक्टमैक्स अधिकतम तत्व (रूट) को अधिकतम हीप से हटा देता है। ऑपरेशन भी ढेर संपत्ति को बनाए रखने के लिए अधिकतम ढेर को ढेर करता है। इस ऑपरेशन की समय जटिलता हे (लॉग एन) है।
# 3) getMax: getMax ऑपरेशन O (1) की समय जटिलता के साथ अधिकतम ढेर का रूट नोड लौटाता है।
नीचे जावा प्रोग्राम अधिकतम ढेर को लागू करता है। हम अधिकतम ढेर तत्वों का प्रतिनिधित्व करने के लिए यहां ArrayList का उपयोग करते हैं।
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); 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; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } 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); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ 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); } }
आउटपुट:
जावा में प्राथमिकता कतार न्यूनतम ढेर
जावा में प्राथमिकता कतार डेटा संरचना का उपयोग सीधे मिन-हीप का प्रतिनिधित्व करने के लिए किया जा सकता है। डिफ़ॉल्ट रूप से, प्राथमिकता कतार न्यूनतम-ढेर को लागू करती है।
नीचे दिया गया कार्यक्रम प्राथमिकता कतार का उपयोग करके जावा में न्यूनतम-ढेर को प्रदर्शित करता है।
import java.util.*; class Main { public static void main(String args[]) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }
आउटपुट:
जावा में प्राथमिकता कतार अधिकतम ढेर
प्राथमिकता कतार का उपयोग करके जावा में अधिकतम ढेर का प्रतिनिधित्व करने के लिए, हमें min-heap को उलटने के लिए Collections.reverseOrder का उपयोग करना होगा। प्राथमिकता कतार सीधे जावा में एक न्यूनतम-ढेर का प्रतिनिधित्व करती है।
हमने नीचे कार्यक्रम में प्राथमिकता कतार का उपयोग करके मैक्स हीप को लागू किया है।
import java.util.*; class Main { public static void main(String args[]) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }
आउटपुट:
हीप को जावा में क्रमबद्ध करें
हीप सॉर्ट, चयन सॉर्ट के समान तुलनात्मक तकनीक है जिसमें हम प्रत्येक पुनरावृत्ति के लिए सरणी में एक अधिकतम तत्व का चयन करते हैं। हीप सॉर्ट हीप डेटा संरचना का उपयोग करता है और सॉर्ट किए जाने वाले एरे तत्वों में से न्यूनतम या अधिकतम हीप बनाकर तत्वों को सॉर्ट करता है।
हमने पहले ही चर्चा की है कि न्यूनतम और अधिकतम ढेर में, रूट नोड में क्रमशः सरणी का न्यूनतम और अधिकतम तत्व होता है। ढेर प्रकार में, ढेर (मिनट या अधिकतम) के मूल तत्व को हटा दिया जाता है और सॉर्ट किए गए सरणी में ले जाया जाता है। बचे हुए ढेर को फिर ढेर संपत्ति बनाए रखने के लिए ढेर कर दिया जाता है।
इसलिए हमें दो चरणों को पुन: व्यवस्थित करना है ताकि दिए गए सरणी को ढेर सॉर्ट का उपयोग किया जा सके।
- दिए गए सरणी से एक ढेर बनाएँ।
- बार-बार जड़ तत्व को ढेर से हटा दें और इसे सॉर्ट किए गए सरणी में ले जाएं। बचे हुए ढेर को ठीक करें।
हीप सॉर्ट की समय जटिलता सभी मामलों में हे (एन लॉग एन) है। अंतरिक्ष जटिलता O (1) है।
हीप सॉर्ट एलगोरिदम इन जावा
नीचे दिए गए आरोही एल्गोरिदम में आरोही और अवरोही क्रम में दिए गए सरणी को क्रमबद्ध करना है।
(1) आरोही क्रम में सॉर्ट करने के लिए हीप सॉर्ट एल्गोरिथ्म:
- दिए गए सरणी के लिए एक अधिकतम ढेर बनाएँ।
- रूट (इनपुट एरे में अधिकतम मूल्य) को हटा दें और इसे सॉर्ट किए गए एरे पर ले जाएं। एरे में अंतिम तत्व को रूट पर रखें।
- ढेर की नई जड़ को ढेर करो।
- चरण 1 और 2 को तब तक दोहराएं जब तक कि संपूर्ण सरणी सॉर्ट न हो जाए।
# 2) ढेर क्रमबद्ध एल्गोरिथ्म को अवरोही क्रम में क्रमबद्ध करना है:
- दिए गए सरणी के लिए एक मिनट हीप का निर्माण करें।
- रूट (सरणी में न्यूनतम मान) निकालें और इसे सरणी में अंतिम तत्व के साथ स्वैप करें।
- ढेर की नई जड़ को ढेर करो।
- चरण 1 और 2 को तब तक दोहराएं जब तक कि संपूर्ण सरणी सॉर्ट न हो जाए।
ढेर जावा में कार्यान्वयन को क्रमबद्ध करें
नीचे जावा प्रोग्राम आरोही क्रम में एक सरणी को सॉर्ट करने के लिए ढेर सॉर्ट का उपयोग करता है। इसके लिए, हम पहले एक अधिकतम ढेर का निर्माण करते हैं और फिर ऊपर के एल्गोरिथ्म में बताए अनुसार रूट एलिमेंट को स्वैप और हाईपाइप करते हैं।
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array[]) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array[0]; heap_Array[0] = heap_Array[i]; heap_Array[i] = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array[], int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array[largest]) largest = left; if (right heap_Array[largest]) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array[i]; heap_Array[i] = heap_Array[largest]; heap_Array[largest] = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args[]) { //define input array and print it int heap_Array[] = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } }
आउटपुट:
हीप सॉर्ट तकनीक की समग्र समय जटिलता हे (nlogn) है। हाइपिफाई तकनीक का समय जटिलता हे (लोगन) है। जबकि ढेर के निर्माण की समय जटिलता O (n) है।
ढेर बनाम ढेर जावा में
आइए अब एक स्टैक डेटा संरचना और ढेर के बीच कुछ अंतरों को सारणीबद्ध करें।
ढेर ढेर एक स्टैक एक रैखिक डेटा संरचना है। एक ढेर एक पदानुक्रमित डेटा संरचना है। LIFO (अंतिम में, पहले आउट) आदेश का पालन करता है। ट्रैवर्सल स्तर के क्रम में है। ज्यादातर स्थिर मेमोरी आवंटन के लिए उपयोग किया जाता है। गतिशील मेमोरी आवंटन के लिए उपयोग किया जाता है। मेमोरी को आकस्मिक रूप से आवंटित किया जाता है। मेमोरी को यादृच्छिक स्थानों में आवंटित किया जाता है। ऑपरेटिंग सिस्टम के अनुसार स्टैक का आकार सीमित है। ऑपरेटिंग सिस्टम द्वारा लागू ढेर के आकार पर कोई सीमा नहीं। स्टैक की स्थानीय चर तक ही पहुँच है। हीप के पास इसके लिए आवंटित वैश्विक चर हैं। स्मृति का आवंटन / निपटान स्वचालित है। आबंटन / निपटारा प्रोग्रामर द्वारा मैन्युअल रूप से किया जाना चाहिए। स्टैक को Arrays, Linked List, ArrayList इत्यादि या किसी अन्य रैखिक डेटा संरचनाओं का उपयोग करके लागू किया जा सकता है। ढेर Arrays या पेड़ों का उपयोग कर कार्यान्वित किया जाता है। कम होने पर रखरखाव का खर्च। अधिक महंगा बनाए रखने के लिए। स्मृति में कमी हो सकती है क्योंकि स्मृति सीमित है। स्मृति की कोई कमी नहीं है, लेकिन स्मृति विखंडन से पीड़ित हो सकता है।
बार बार पूछे जाने वाले प्रश्न
Q # 1) ढेर से तेज है?
उत्तर: ढेर की तुलना में एक स्टैक तेजी से होता है क्योंकि ढेर की तुलना में स्टैक में पहुंच रैखिक होती है।
Q # 2) एक ढेर का उपयोग किसके लिए किया जाता है?
उत्तर: हीप का उपयोग ज्यादातर एल्गोरिदम में किया जाता है, जो कि डायजेस्ट्रा के एल्गोरिथ्म जैसे दो बिंदुओं के बीच न्यूनतम या सबसे छोटा रास्ता ढूंढता है, जैसे हीप सॉर्ट का उपयोग करना, प्राथमिकता कतार कार्यान्वयन (न्यूनतम-ढेर), आदि के लिए।
Q # 3) ढेर क्या है? इसके प्रकार क्या हैं?
उत्तर: एक ढेर एक पदानुक्रमित, पेड़-आधारित डेटा संरचना है। एक ढेर एक पूर्ण बाइनरी पेड़ है। हीप्स दो प्रकार के होते हैं यानी मैक्स हीप जिसमें रूट नोड सभी नोड्स में सबसे बड़ा होता है; मिन हीप जिसमें सभी कीज़ के बीच रूट नोड सबसे छोटा या न्यूनतम होता है।
क्यू # 4) ढेर पर ढेर के क्या फायदे हैं?
उत्तर: ढेर के ढेर का मुख्य लाभ ढेर में है, स्मृति को गतिशील रूप से आवंटित किया जाता है और इसलिए स्मृति का कितना उपयोग किया जा सकता है इसकी कोई सीमा नहीं है। दूसरे, ढेर पर केवल स्थानीय चर आवंटित किए जा सकते हैं जबकि हम ढेर पर वैश्विक चर भी आवंटित कर सकते हैं।
क्यू # 5) क्या हीप डुप्लिकेट हो सकता है?
उत्तर: हां, ढेर में डुप्लिकेट चाबियों के साथ नोड्स होने पर कोई प्रतिबंध नहीं है क्योंकि ढेर एक पूर्ण बाइनरी ट्री है और यह बाइनरी सर्च ट्री के गुणों को संतुष्ट नहीं करता है।
निष्कर्ष
इस ट्यूटोरियल में, हमने ढेर के प्रकारों का उपयोग करके ढेर और हीप प्रकार की चर्चा की है। हमने जावा में इसके प्रकारों के विस्तृत कार्यान्वयन को भी देखा है।
=> यहाँ बिल्कुल सही जावा प्रशिक्षण गाइड देखें।
अनुशंसित पाठ
- जावा ग्राफ ट्यूटोरियल - ग्राफ़ डेटा संरचना को कैसे लागू करें
- C ++ में डेटा स्ट्रक्चर्स का परिचय
- उदाहरणों के साथ C ++ में ढेर छाँटें
- AVL ट्री और ढेर डेटा संरचना C ++ में
- सी + + में बाइनरी ट्री डेटा संरचना
- चित्रण के साथ C ++ में कतार डेटा संरचना
- चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
- जावा बेसिक्स: जावा सिंटैक्स, जावा क्लास और कोर जावा कॉन्सेप्ट