data-structures
बाइनरी हीप
खोज…
परिचय
एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है जो हीप ऑर्डर करने वाली संपत्ति को संतुष्ट करता है। आदेश दो प्रकारों में से एक हो सकता है: न्यूनतम-ढेर संपत्ति: प्रत्येक नोड का मूल्य मूल में न्यूनतम मूल्य तत्व के साथ, अपने माता-पिता के मूल्य से अधिक या बराबर होता है।
उदाहरण
मिन-ढेर
1
/ \
2 3
/ \ / \
4 5 6 7
उपरोक्त पेड़ एक मिन-हीप है क्योंकि जड़ पेड़ में मौजूद सभी नोड्स में न्यूनतम है। उसी संपत्ति का पालन पेड़ के सभी नोड्स द्वारा किया जाता है।
अधिकतम ढेर
7
/ \
6 5
/ \ / \
4 3 2 1
उपरोक्त पेड़ एक मैक्स-हीप है क्योंकि जड़ पेड़ में मौजूद सभी नोड्स में अधिकतम है। उसी संपत्ति का पालन पेड़ में सभी नोड्स द्वारा किया जाता है।
संचालन मिन-हीप द्वारा समर्थित है
getMin () - यह मूल तत्व को लौटाता है। मान लीजिए कि यह एक सरणी में पहला तत्व है जिसे हम
O(1)में न्यूनतम तत्व प्राप्त कर सकते हैं।extractMin () - यह हीप से न्यूनतम तत्व को निकालता है। तत्व को हटाने के बाद पेड़ को मिन-हीप संपत्ति को संतुष्ट करना होगा ताकि ट्री प्रॉपर्टी को बनाए रखने के लिए एक ऑपरेशन ( हीपिंग ) किया जाए। यह
O(logn)लेता हैdereaseKey () - यह कुंजी का मान घटाता है। इस ऑपरेशन के लिए समय जटिलता
O(logn)सम्मिलित करें () - कुंजी हमेशा पेड़ के अंत में डाली जाती है। यदि अतिरिक्त कुंजी ढेर संपत्ति का पालन नहीं करती है, तो हमें जरूरत है कि हम ऊपर की ओर झुकें, ताकि पेड़ ढेर संपत्ति को संतुष्ट कर सके। यह कदम
O(logn)लेता है। समय।डिलीट () - इस स्टेप्स में
O(logn)टाइम लगता है। कुंजी को डिलीट करने के लिए हमें सबसे पहले महत्वपूर्ण मूल्य को एक न्यूनतम मूल्य में घटाना होगा और फिर इस न्यूनतम मूल्य को निकालना होगा।
हीप का अनुप्रयोग
- ढेर बनाएं और छांटें
- प्राथमिकता कतार
हीप का उपयोग कई एल्गोरिदम जैसे कि Dijkstra's Shortest Path और Prim's Minimum Spanning Tree ।
जावा में कार्यान्वयन
public class MinHeap {
int hArr[];
int capacity;
int heapSize;
public MinHeap(int capacity){
this.heapSize = 0;
this.capacity = capacity;
hArr = new int[capacity];
}
public int getparent(int i){
return (i-1)/2;
}
public int getLeftChild(int i){
return 2*i+1;
}
public int getRightChild(int i){
return 2*i+2;
}
public void insertKey(int k){
if(heapSize==capacity)
return;
heapSize++;
int i = heapSize-1;
hArr[i] = k;
while(i!=0 && hArr[getparent(i)]>hArr[i]){
swap(hArr[i],hArr[getparent(i)]);
i = getparent(i);
}
}
public int extractMin(){
if(heapSize==0)
return Integer.MAX_VALUE;
if(heapSize==1){
heapSize--;
return hArr[0];
}
int root = hArr[0];
hArr[0] = hArr[heapSize-1];
heapSize--;
MinHeapify(0);
return root;
}
public void decreaseKey(int i , int newVal){
hArr[i] = newVal;
while(i!=0 && hArr[getparent(i)]>hArr[i]){
swap(hArr[i],hArr[getparent(i)]);
i = getparent(i);
}
}
public void deleteKey(int i){
decreaseKey(i, Integer.MIN_VALUE);
extractMin();
}
public void MinHeapify(int i){
int l = getLeftChild(i);
int r = getRightChild(i);
int smallest = i;
if(l<heapSize && hArr[l] < hArr[i])
smallest = l;
if(l<heapSize && hArr[r] < hArr[smallest])
smallest = r;
if(smallest!=i){
swap(hArr[i], hArr[smallest]);
MinHeapify(smallest);
}
}
public void swap(int x, int y){
int temp = hArr[x];
hArr[x] = hArr[y];
hArr[y] = temp;
}
}