File D'Attente De Priorité Tas De Mise En Œuvre
Je suis en train d'écrire le code à implémenter une file d'attente de priorité à l'aide d'un tas. Quand je rentre d'éléments dans la file d'attente avec ces priorités dans cet ordre spécifique 8 10 4 3 7 6 9 5
j'obtiens une erreur lorsque je commence à éclater entre eux avec de la get_front()
fonction.
Le problème est qu'une assertion échoue pour la swap_with_parent()
fonction dans le while
-boucle de la get_front()
fonction . L'argument est en quelque sorte de plus en plus que le nombre d'éléments dans le tableau, many_items. Je vais poster tout le code, si quelqu'un peut repérer un problème je vous en serais reconnaissant si vous pouviez me le faire savoir. Je m'excuse à l'avance pour le manque de commentaires, j'espère que c'est assez clair ce que j'ai eu en cours.
//INVARIANT for the PriorityQueue Class:
// 1. The member variable many_items is the number of items in the
// PriorityQueue.
// 2. The items themselves are stored in the member variable heap,
// which is a partially filled array organized to follow the usual
// heap storage rules from Chapter 11 of the class notes.
//NOTE: Private helper functions are implemented at the bottom of this
//file along with their precondition/postcondition contracts.
#include <assert.h> //Provides assert function
#include <iomanip> //Provides setw
#include <iostream> //Provides cin, cout
#include <math.h> //Provides log2
#include "pqueue2.h"
using namespace std;
PriorityQueue::PriorityQueue( )
{
heap[CAPACITY];
many_items=0;
}
void PriorityQueue::insert(const Item& entry, unsigned int priority)
{
if(many_items==0)
{
heap[many_items].data= entry;
heap[many_items].priority= priority;
many_items++;
}
else
{
heap[many_items].data= entry;
heap[many_items].priority= priority;
unsigned int i= many_items;
many_items++;
while(parent_priority(i)<priority)
{
swap_with_parent(i);
i=parent_index(i);
}
}
}
PriorityQueue::Item PriorityQueue::get_front( )
{
assert(many_items>0);
if(many_items==1)
{
Item front_value=heap[0].data;
many_items--;
return front_value;
}
else
{
Item front_value=heap[0].data;
heap[0]=heap[many_items-1];
unsigned int priority= heap[many_items-1].priority;
unsigned int k=0;
while( (k<many_items) && !is_leaf(k) && big_child_priority(k)>priority)
{
unsigned int j=big_child_index(k);
swap_with_parent(big_child_index(k));
k= j;
}
many_items--;
return front_value;
}
}
bool PriorityQueue::is_leaf(size_t i) const
//Precondition: (i < many_items)
//Postcondition: If heap[i] has no children in the heap, then the function
//returns true. Otherwise the function returns false.
{
if(((2*i)+1)>many_items)
return 1;
else
return 0;
}
size_t PriorityQueue::parent_index(size_t i) const
//Precondition: (i > 0) && (i < many_items)
//Postcondition: The return value is the index of the parent of heap[i].
{
//assert( /*(i>0) && */(i<many_items));
return (i-1)/2;
}
unsigned int PriorityQueue::parent_priority(size_t i) const
//Precondition: (i > 0) && (i < many_items)
//Postcondition: The return value is the priority of the parent of heap[i].
{
return heap[ (i-1)/2].priority;
}
size_t PriorityQueue::big_child_index(size_t i) const
//Precondition: !is_leaf(i)
//Postcondition: The return value is the index of one of heap[i]'s children.
//This is the child with the larger priority.
{
assert(!is_leaf(i));
if((2*i)+2<many_items)
{
if(heap[(2*i)+1].priority>heap[(2*i)+2].priority)
{
return (2*i)+1;
}
else
{
return (2*i)+2;
}
}
else
{
return(2*i)+1;
}
}
unsigned int PriorityQueue::big_child_priority(size_t i) const
//Precondition: !is_leaf(i)
//Postcondition: The return value heap[big_child_index(i)].priority
{
return heap[big_child_index(i)].priority;
}
void PriorityQueue::swap_with_parent(size_t i)
//Precondition: (i > 0) && (i < many_items)
//Postcondition: heap[i] has been swapped with heap[parent_index(i)]
{
assert( i>0 && i<many_items);
OneItemInfo temp_parent=heap[parent_index(i)];
OneItemInfo temp_child=heap[i];
heap[i]=temp_parent;
heap[parent_index(i)]=temp_child;
}
En plus de @BjörnPollex, suivez ce lien: cs.baylor.edu/~donahoo/tools/gdb/tutorial.html
Quel est le but de la ligne
heap[CAPACITY];
dans votre constructeur?
OriginalL'auteur Mike | 2012-05-15
Vous devez vous connecter pour publier un commentaire.
Je pense que
is_leaf
est incorrect. La condition doit être(2*i+1 >= many_items)
.la vieille mise en œuvre permettrait la
while
boucle dansget_front
être entré pour unk
avec2*k+1 == many_items
.big_child_index
sera de retourmany_items
et il est ensuite passé àswap_with_parent
.OriginalL'auteur Henrik