Est-ce que je mets en œuvre l'algorithme "Heapify" correctement?
Je suis de la création d'un tas de mise en œuvre pour une classe informatique, et je me demandais si la fonction récursive serait de créer un tas de sortir d'un objet de tableau qui n'était pas déjà un tas.
le code est comme suit:
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);
}
}
l'idée est que vous voyez si les données sur l'indice donné est plus grand que tous ses enfants. Si c'est le cas, la fonction se termine pas de problème. Sinon, vérifier pour voir qui est le plus grand(de droite ou de gauche, les enfants), puis d'échanges avec l'index. Le heapify est alors appelé à l'index où l'échange qui s'est passé.
par ildjarn sa demande, je suis, y compris ma classe complète la définition et la mise en œuvre des fichiers à l'aide à la réponse de ma question:
voici le fichier d'en-tête:
#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
et la mise en œuvre de fichier:
#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];
}
}
source d'informationauteur Chris De Bow | 2011-11-15
Vous devez vous connecter pour publier un commentaire.
Votre algorithme fonctionne. Le problème est dans la traduction de l'algorithme de code. Dire que vous avez déclaré des Données :
et vous remplir avec les valeurs initiales
{0, 1, 2, 3, 4, 5, 6}
. En supposant définitions deLeftChild(i)
etRightChild(i)
être quelque chose comme:alors votre fonction
BuildHeap()
qui doit être quelque chose comme:commencera le
Heapify
processus dans le coin inférieur droit de la plupart des sous-arbre de racine. Dans ce cas, c'est l'index du tableau 2, avec à gauche des enfants de 5 et un droit de l'enfant de 6.Heapify
correctement échange 2 et 6, et de manière récursive appelHeapify(6)
.Ici, le tout peut s'échouer! À l'heure actuelle de votre arbre ressemble :
donc, l'appel
Heapify(6)
seront consciencieusement comparer les valeurs deData[6]
avecData[13]
etData[14]
(les dangers de C++ et de son manque de tableau des limites d'application, contrairement à Java). Évidemment, les deux dernières valeurs peuvent être une ordure gauche dans la mémoire RAM. Une seule solution ici, laid, mais un patch de travail, est d'ajouter 8 éléments dans la déclaration des Données et de les initialiser tous à une valeur inférieure à n'importe quel élément de la matrice. La meilleure solution est d'ajouter uneheapSize
variable de votre classe et de définir égale à la longueur de votre tableau:Ensuite intégrer la logique de comparer uniquement les nœuds enfants s'ils sont valides feuilles de l'arbre. Une mise en œuvre efficace de la présente est :
Donc, pour résumer, la solution est aussi simple que l'ajout de la logique pour s'assurer que l'enfant nœuds sont valables feuilles de l'arbre, et votre fonction principale sera quelque chose comme :
Espère que ça aide.
Pas. Sur l'arbre
la sortie va être
qui a plusieurs tas de violations. (Je suis en supposant que
Data[l]
etData[r]
sont moins l'infini si les enfants n'existent pas. Vous avez peut-être besoin de plus logique pour s'en assurer.)Ce que votre fonction n'est fix un arbre qui ne peut pas être un tas, mais dont les sous-arbres gauche et droit sont des tas. Vous avez besoin de l'appeler sur chaque nœud, en postorder (c'est à dire, pour i de n - 1 à 0) de sorte que les enfants de i sont des tas lors de Heapify(i) est appelée.