हीप डेटा स्ट्रक्चर

इस ट्यूटोरियल में, आप सीखेंगे कि डेटा संरचना क्या है। इसके अलावा, आप सी, सी ++, जावा और पायथन में ढेर के संचालन के काम के उदाहरण पाएंगे।

हीप डेटा संरचना एक पूर्ण बाइनरी ट्री है जो ढेर संपत्ति को संतुष्ट करती है । इसे बाइनरी हीप भी कहा जाता है ।

पूर्ण बाइनरी ट्री एक विशेष बाइनरी ट्री है जिसमें

• हर स्तर, संभवतः अंतिम को छोड़कर, भरा हुआ है
• सभी नोड्स यथासंभव शेष हैं

हीप प्रॉपर्टी एक नोड की संपत्ति है जिसमें

• (अधिकतम ढेर के लिए) प्रत्येक नोड की कुंजी हमेशा अपने बच्चे के नोड / एस से अधिक होती है और रूट नोड की कुंजी अन्य सभी नोड्स में सबसे बड़ी होती है;
  
• (मिन हीप के लिए) प्रत्येक नोड की कुंजी हमेशा बच्चे के नोड / एस से छोटी होती है और रूट नोड की कुंजी अन्य सभी नोड्स में सबसे छोटी होती है।

ढेर संचालन

ढेर पर किए गए कुछ महत्वपूर्ण संचालन उनके एल्गोरिदम के साथ नीचे वर्णित हैं।

ढेर करो

Heapify एक बाइनरी ट्री से हीप डेटा संरचना बनाने की प्रक्रिया है। इसका उपयोग मिन-हीप या मैक्स-हीप बनाने के लिए किया जाता है।

1. इनपुट ऐरे को होने दें
   
2. सरणी से एक पूर्ण बाइनरी ट्री बनाएं
   
3. गैर-पत्ती नोड के पहले सूचकांक से शुरू करें जिसका सूचकांक द्वारा दिया गया है n/2 - 1।
   
4. वर्तमान तत्व के iरूप में सेट करें largest।
5. बाएं बच्चे का सूचकांक द्वारा दिया गया है 2i + 1और दाएं बच्चे द्वारा दिया गया है 2i + 2।
   यदि ( इंडेक्स पर तत्व ) leftChildसे अधिक है , तो सबसे बड़ा सेट करें । यदि तत्व से अधिक है , तो इस रूप में सेट करें ।currentElementithleftChildIndex
rightChildlargestrightChildIndexlargest
6. के largestसाथ स्वैप करेंcurrentElement
   
7. चरण 3-7 तब तक दोहराएं जब तक कि सबटाइटल भी ढेर न हो जाएं।

कलन विधि

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

मैक्स-हीप बनाने के लिए:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

मिन-हीप के लिए, दोनों leftChildऔर rightChildसभी नोड्स के लिए माता-पिता से छोटा होना चाहिए।

तत्व को ढेर में डालें

मैक्स हीप में सम्मिलन के लिए एल्गोरिदम

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array

1. पेड़ के अंत में नया तत्व डालें।
   
2. पेड़ को ढेर करो।

मिन हीप के लिए, उपरोक्त एल्गोरिथ्म को संशोधित किया गया है ताकि parentNodeहमेशा की तुलना में छोटा हो newNode।

हीप से तत्व हटाएं

मैक्स हीप में विलोपन के लिए एल्गोरिदम

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array

1. हटाए जाने वाले तत्व का चयन करें।
   
2. अंतिम तत्व के साथ इसे स्वैप करें।
   
3. अंतिम तत्व निकालें।
   
4. पेड़ को ढेर करो।

मिन हीप के लिए, ऊपर एल्गोरिथ्म को संशोधित किया गया है ताकि दोनों की childNodesतुलना में अधिक छोटा हो currentNode।

पीक (अधिकतम / मिनट ढूंढें)

पीक ऑपरेशन नोड को हटाए बिना अधिकतम हीप से अधिकतम तत्व या न्यूनतम हीप से न्यूनतम तत्व देता है।

मैक्स हीप और मिन हीप दोनों के लिए

 रूटकोड वापस करें

एक्सट्रेक्ट-मैक्स / मिन

एक्सट्रे-मैक्स नोड को मैक्स हीप से हटाने के बाद अधिकतम मान के साथ लौटाता है जबकि एक्स्ट-मिन नोड को मिनिप से हटाने के बाद न्यूनतम के साथ नोड लौटाता है।

पायथन, जावा, सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # Max-Heap data structure in Python def heapify(arr, n, i): 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 if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) 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) 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(num) 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)) 

  // Max-Heap data structure in Java 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(); ) 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); ) )

 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( 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; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) 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); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) 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); ) 

 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); 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; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) 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); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) 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); ) 

हीप डेटा स्ट्रक्चर एप्लिकेशन

• प्राथमिकता कतार को लागू करते समय हीप का उपयोग किया जाता है।
• डीजकस्ट्रा का एल्गोरिथम
• ढेर बनाएं और छांटें