एक हीप एक पूर्ण बाइनरी ट्री है जो या तो मिन हीप या मैक्स हीप है। एक मैक्स हीप में, रूट पर कुंजी हीप में मौजूद सभी कुंजियों में अधिकतम होनी चाहिए। यह गुण उस बाइनरी ट्री में सभी नोड्स के लिए पुनरावर्ती रूप से सत्य होना चाहिए। मिन हीप मिनहीप के समान है।
फंक्शन विवरण
void BHeap::Insert(int ele): हीप में तत्व डालने के लिए सम्मिलन ऑपरेशन करें।
void BHeap::DeleteMin(): हीप से न्यूनतम मान हटाने के लिए विलोपन ऑपरेशन करें।
int BHeap::ExtractMin(): हीप से न्यूनतम मान निकालने के लिए ऑपरेशन करें।
void BHeap::showHeap(): हीप के तत्व दिखाने के लिए।
void BHeap::heapifyup(int in): नीचे से ऊपर की तरीके से हीप संरचना बनाए रखें।
void BHeap::heapifydown(int in): ऊपर से नीचे की तरीके से हीप संरचना बनाए रखें।
उदाहरण
#include <iostream> #include <cstdlib> #include <vector> #include <iterator> using namespace std; class BHeap { private: vector <int> heap; int l(int parent); int r(int parent); int par(int child); void heapifyup(int in); void heapifydown(int in); public: BHeap() {} void Insert(int element); void DeleteMin(); int ExtractMin(); void showHeap(); int Size(); }; int main() { BHeap h; while (1) { cout<<"1.तत्व डालें"<<endl; cout<<"2.न्यूनतम तत्व हटाएं"<<endl; cout<<"3.न्यूनतम तत्व निकालें"<<endl; cout<<"4.हीप दिखाएं"<<endl; cout<<"5.बाहर निकलें"<<endl; int c, e; cout<<"अपनी पसंद दर्ज करें: "; cin>>c; switch(c) { case 1: cout<<"डालने के लिए तत्व दर्ज करें: "; cin>>e; h.Insert(e); break; case 2: h.DeleteMin(); break; case 3: if (h.ExtractMin() == -1) { cout<<"हीप खाली है"<<endl; } else cout<<"न्यूनतम तत्व: "<<h.ExtractMin()<<endl; break; case 4: cout<<"हीप के तत्व प्रदर्शित: "; h.showHeap(); break; case 5: exit(1); default: cout<<"सही विकल्प दर्ज करें"<<endl; } } return 0; } int BHeap::Size() //हीप का आकार { return heap.size(); } void BHeap::Insert(int ele) //हीप में तत्व डालें { heap.push_back(ele);//तत्व को हीप में पुश करें heapifyup(heap.size() -1);//हीप संरचना बनाए रखने के लिए heapifyup() कॉल करें } void BHeap::DeleteMin() //हीप से न्यूनतम मान हटाएं { if (heap.size() == 0) { cout<<"हीप खाली है"<<endl; return; } heap[0] = heap.at(heap.size() - 1); heap.pop_back();//तत्व पॉप करें heapifydown(0); cout<<"तत्व हटाया गया"<<endl; } int BHeap::ExtractMin() //हीप से न्यूनतम मान निकालें { if (heap.size() == 0) { return -1; } else return heap.front(); } void BHeap::showHeap() //हीप के तत्व दिखाएं { vector <int>::iterator pos = heap.begin(); cout<<"हीप --> "; while (pos != heap.end()) { cout<<*pos<<" "; pos++; } cout<<endl; } int BHeap::l(int parent) // नोड का बायां बच्चा वापस करें। { int l = 2 * parent + 1; if (l < heap.size()) return l; else return -1; } int BHeap::r(int parent) // नोड का दायां बच्चा वापस करें। { int r = 2 * parent + 2; if (r < heap.size()) return r; else return -1; } int BHeap::par(int child)// माता-पिता वापस करें { int p = (child - 1)/2; if (child == 0) return -1; else return p; } void BHeap::heapifyup(int in)//नीचे से ऊपर की तरीके से हीप संरचना बनाए रखें। { if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) { int temp = heap[in]; heap[in] = heap[par(in)]; heap[par(in)] = temp; heapifyup(par(in)); } } void BHeap::heapifydown(int in)//ऊपर से नीचे की तरीके से हीप संरचना बनाए रखें। { int child = l(in); int child1 = r(in); if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) { child = child1; } if (child > 0 && heap[in] > heap[child]) { int t = heap[in]; heap[in] = heap[child]; heap[child] = t; heapifydown(child); } }
आउटपुट
1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 1 डालने के लिए तत्व दर्ज करें: 2 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 1 डालने के लिए तत्व दर्ज करें: 3 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 1 डालने के लिए तत्व दर्ज करें: 7 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 1 डालने के लिए तत्व दर्ज करें: 6 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 4 हीप के तत्व प्रदर्शित: हीप --> 2 3 7 6 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 3 न्यूनतम तत्व: 2 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 3 न्यूनतम तत्व: 2 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 2 तत्व हटाया गया 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 4 हीप के तत्व प्रदर्शित: हीप --> 3 6 7 1.तत्व डालें 2.न्यूनतम तत्व हटाएं 3.न्यूनतम तत्व निकालें 4.हीप दिखाएं 5.बाहर निकलें अपनी पसंद दर्ज करें: 5
