16
मैं कंप्यूटर विज्ञान वर्ग के लिए एक ढेर कार्यान्वयन कर रहा हूं, और मैं सोच रहा था कि निम्नलिखित रिकर्सिव फ़ंक्शन एक सरणी ऑब्जेक्ट से ढेर बना देगा जो पहले से ही ढेर नहीं था। कोड इस प्रकार है:क्या मैं "हेपीफाइ" एल्गोरिदम सही ढंग से कार्यान्वित कर रहा हूं?
void Heap::Heapify(int i)
{
int temp, l, r, heapify;
l = LeftChild(i);// get the left child
r = RightChild(i);// get the right child
//if one of the children is bigger than the index
if((Data[i] < Data[l]) || (Data[i]< Data[r]))
{
//if left is the bigger child
if(Data[l] > Data[r])
{
//swap parent with left child
temp = Data[i];
Data[i] = Data[l];
Data[l] = temp;
heapify = l; // index that was swapped
}
//if right is the bigger child
else
{
//swap parent with right child
temp = Data[i];
Data[i] = Data[r];
Data[r] = temp;
heapify = r; // index that was swapped
}
// do a recursive call with the index
//that was swapped
Heapify(heapify);
}
}
विचार यह है कि यदि आप देखते हैं दिए गए इंडेक्स पर डेटा बड़ा की तुलना में यह के सभी बच्चों है है। यदि ऐसा है, तो फ़ंक्शन कोई समस्या नहीं समाप्त होता है। अन्यथा, यह देखने के लिए जांचें कि कौन सा सबसे बड़ा (बाएं या दाएं बच्चे) है, और उसके बाद सूचकांक के साथ स्वैप करता है। तब हेपफाइफ़ को इंडेक्स में बुलाया जाता है जहां स्वैपिंग हुई।
#ifndef HEAP_H
#define HEAP_H
//Programmer: Christopher De Bow
//Date: november 15, 2011
class Heap
{
private:
int Data [100];
int Parent(int);
int RightChild(int);
int LeftChild(int);
void Heapify(int);
void BuildHeap();
public:
Heap();
void insert();
void HeapSort();
void ExtractMaximum();
int Maximum();
void PrintHeap();
int heapsize;
void SetData(int[]);
};
#endif
और कार्यान्वयन फ़ाइल:
यहाँ हेडर फाइल है:
ildjarn के अनुरोध से, मैं अपने सवाल का जवाब देने में सहायता करने के मेरा पूरा वर्ग परिभाषा और कार्यान्वयन फ़ाइलों सहित कर रहा हूँ
#include <iostream>
#include "Heap.h"
using namespace std;
//Programmer: Christopher De Bow
//Date: november 15, 2011
Heap::Heap()
{
int init [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
heapsize = 10;
SetData(init);
}
int Heap::Parent(int index)
{
int Rval;
if(index%2 == 0)// if the index is even
{
Rval = ((index-1)/2);
}
else// if the index is odd
{
Rval = (index/2);
}
return Rval;
}
int Heap::RightChild(int arrplace)
{
int ret;
ret = ((2*arrplace)+2); //rightchild is index times 2 plus 2
return ret;
}
int Heap::LeftChild(int i)
{
int rval;
rval = ((2*i)+1); //leftchild is index times 2 plus 1
return rval;
}
void Heap::Heapify(int i)
{
int temp, l, r, heapify;
l = LeftChild(i); // get the left child
r = RightChild(i); // get the right child
if((l <= heapSize) && (data[l] > data[i]))
{
heapify = l;
{
else
{
heapfiy = i;
}
if((r <= heapSize) && (data[r] > data[heapify]))
{
heapify = r;
}
if(heapify != i) // one of the two child nodes has proved
{ // larger than Data[i], so interchange values
//swap parent with left child
temp = Data[i];
Data[i] = Data[heapify];
Data[heapify] = temp;
Heapify(heapify);
}
}
void Heap::BuildHeap()
{
// we do not have a heap
// we will make a heap
// by calling heapify starting at the lowest
// internal node in the heap
for(int i = heapsize; i >= 1; i--)
{
Heapify(i-1);
}
}
void Heap::insert()
{
int insert;
heapsize = (heapsize + 1);
//getting data from the user
cout<<"what data would you like to insert?"<<endl;
cin>>insert;
Data[heapsize] = insert;
BuildHeap(); //call BuildHeap on array
cout<<"done"<<endl;
}
void Heap::PrintHeap()
{
BuildHeap();
for(int count = 0; count < (heapsize-1); count++)
{
cout<<Data[count];// print out every element in heap
}
cout<<endl<<endl;
}
void Heap::HeapSort()
{
BuildHeap();
int temp;
// do this for every elem in heap:
for(int i = 0; i < heapsize; i++)
{
temp = Data[heapsize-1];
Data[heapsize-1] = Data[0];
Data[0] = temp;
heapsize--;
BuildHeap();
}
PrintHeap();
}
void Heap::ExtractMaximum()
{
BuildHeap();
//assign last thing in heap to first thing in heap
Data[0] = Data[heapsize];
heapsize --; // decrease heapsize by one
Heapify(0); // heapify from the top
}
int Heap::Maximum()
{
int Rval;
BuildHeap();// make sure we have a heap
Rval = Data[0];
return Rval; // return top thing
}
//initialize the elements in the "Data" array
void Heap::SetData(int x[])
{
for(int i = 0; i <= (heapsize); i++)
{
Data[i] = x[i];
}
}
आहा! प्रयास के सबूत के साथ एक होमवर्क सवाल!+1 – vcsjones
डी ओह, बहुत बहुत धन्यवाद! –
@vcsjones: वास्तव में, दुख की बात है एक दुर्लभता। – ildjarn