16
Tworzę implementację sterty dla klasy informatycznej i zastanawiałem się, czy następująca funkcja rekursywna tworzy stertę z obiektu tablicy, który nie był już stertą. kod jest w następujący sposób:Czy poprawnie wprowadzam algorytm "Heapify"?
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);
}
}
chodzi o to, że widać, jeśli dane w indeksie danej jest większa niż wszystkich jego dzieci. Jeśli tak, funkcja nie kończy problemu. W przeciwnym razie sprawdza, który jest największy (lewy lub prawy potomek), a następnie zamienia go z indeksem. Stertylizacja jest następnie wywoływana w indeksie, w którym nastąpiło zamiana.
życzenie Ildjarn za, jestem w tym moje pełne określaniu i urzeczywistnianiu klasa plików, aby ułatwić odpowiadanie na moje pytanie:
oto nagłówek pliku:
#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
a plik realizacja:
#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];
}
}
Yay! Pytanie o zadanie domowe z dowodami wysiłku!+1 – vcsjones
D'aww, dziękuję bardzo! –
@vcsjones: Rzeczywiście, niestety rzadkość. – ildjarn