Suis-je mise en œuvre de la “Heapify” Algorithme 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];
}
}
- Yay!!! Devoirs à faire à la question avec la preuve de l'effort! +1
- D'aww, merci beaucoup!
- En effet, malheureusement, une rareté.
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 comme :
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.
Votre code maintenant avec succès construit un tas. Il n'y avait qu'une faille conceptuelle : le reste a été tout-en-un les erreurs d'indexation. Une erreur fondamentale a été de BuildHeap : vous avez eu
alors que cela devrait être
Ce qui est vraiment important, vous devez voir que Heapify est toujours appelée sur une racine d'arbre, et (c'est vraiment cool), vous pouvez facilement trouver la dernière racine de l'arbre dans le tableau à l'index ((heapSize/2) - 1) (c'est pour C++ et Java de style où le premier index == 0). La façon dont il a été écrit votre code appelé Heapify sur la dernière feuille de l'arbre, qui est dans l'erreur.
Autre que cela, j'ai ajouté des commentaires pour marquer le tout-en-un d'erreurs. Je les ai placés aligné à gauche de sorte que vous pouvez facilement les trouver. J'espère que vous obtenez un modèle superbe compréhension des algorithmes et structures de données! 🙂
Votre fichier d'en-tête :
Votre fichier cpp :
Votre code comme écrit ici, assurez-vous se sent droit; mais il n'y a rien tout à fait comme la rédaction d'un peu de cas de test pour voir comment il se comporte. Assurez-vous de tester contre un tas avec 1, 2, 3, 4, et des dizaines d'éléments. (J'attends la base de cas où ce morceau est court-comment ça poignée lorsque
i
n'a pas d'enfants?. Des tests sur des petits tas doit montrer pressé.)Quelques petits conseils pour cette pièce:
Vous pourriez probablement acquérir une certaine lisibilité en paramètre uniquement le indice dans le
if
blocs:LeftChild
ouRightChild
, ou dans la façon dontData
est déclarée.