16
Estoy creando una implementación de montón para una clase de ciencias de la computación, y me preguntaba si la siguiente función recursiva crearía un montón de un objeto de matriz que ya no era un montón. el código es el siguiente:¿Estoy implementando correctamente el algoritmo "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);
}
}
la idea es que a ver si los datos en el índice dado es más grande que todo eso de los niños. Si lo es, la función no termina ningún problema. De lo contrario, verifica cuál es el más grande (hijos izquierdos o derechos) y luego lo intercambia con el índice. El heapify se llama en el índice donde sucedió el intercambio.
por la petición de Ildjarn, Estoy incluyendo mis archivos completos de definición de clase y de implementación para ayudar en el contestador de mi pregunta:
aquí está el archivo de cabecera:
#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
y el archivo de implementación:
#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! ¡Una pregunta de tarea con evidencia de esfuerzo!+1 – vcsjones
D'aww, ¡muchas gracias! –
@vcsjones: De hecho, lamentablemente una rareza. – ildjarn