[C++] Code di massima priorità

[AntonellaC]

Ciao a tutti! Ho un problema con il seguente programma C++, lo scopo era quella di creare una coda di max priorità a partire da n numeri e di estrarre i k numeri più grandi chiamando k volte la procedura extract-max. Per farlo ho utilizzato la struttura dati heap, e le procedure ad essa correlate tra cui heap-extract-max per determinare i k numeri più grandi. Il problema è che per alcuni input non funziona, tipo se n=7 e k=7. Ho provato a cercare l'errore ma non riesco ad individuarlo, quindi se qualcuno ci riuscisse gliene sarei grata!Grazie!
Ecco il codice:

#include<stdlib.h>
#include<iostream>
#include <ctime>

using namespace std;

int parent (int i) {return (i+1)/2;}  //determina l'indice del padre,
int left (int i){return ((2*i)+1);}   //del figlio sinistro
int right (int i) {return ((2*i)+2);} //e del figlio destro del nodo i


void MaxHeapify (int A[], int i, int heapsize)
{    
   int l=0, r=0, max=i;
   l=left(i);
   r=right(i);
   if (l<heapsize && A[l]>A[i])   //determina l'elemento maggiore tra A[i] e il figlio sinistro
     max=l;
     else max=i;
   if (r<heapsize && A[r]>A[max]) //determina l'elemento maggiore tra il figlio destro 
     max=r;                       // e il max attuale
   if (max!=i)                   //se uno dei nodi figli è il max
     {swap (A[i], A[max]);       //viene scambiato col padre
      MaxHeapify (A, max, heapsize); // e viene chiamata la MaxHeapify sulla
           }                         // posizione del padre
}

void BuildMaxHeap (int A[], int dim)  
{    for (int i=(dim/2)-1;i>=0;i--) //chiama MaxHeapify su tutti i nodi non foglia
       MaxHeapify(A,i,dim);
     }
void HeapExtractMax (int A[],int max, int dim,int i)
{
   int heapsize=dim;
   BuildMaxHeap (A,dim);
   max=A[0];                //estrae l'elemento massimo 
   cout<<"max"<<i+1<<":"<<max<<'\n';
   heapsize--;          //decrementa la dimensione dell'heap
   A[0]=A[heapsize];// posizione l'ultimo elemento dell'heap nella radice
   //heapsize--;
   MaxHeapify (A,0,heapsize); //chiama MaxHeapify per ripristinare l'ordinamento parziale
}          

 void print(int A[],int n) {  // funzione che stampa a video il vettore A[] generato
  for (int i = 0; i < n; i++) {
     cout<<"A["<<i+1<<"]="<<A[i]<<'\n';
  }
  cout << endl;
}           


      
int main()
{
    int a,b,k;
    clock_t t1;
    clock_t t2;
    int timepast;
    
    cout<<"Procedura che determina i k numeri piu' grandi in un insieme di n numeri.\n\n";
    cout<<"Inserire la dimensione n del vettore di input:\n";
    cin>>a;
    cout<<"Inserire il valore di k:\n";
    cin>>k;
    
    int A[a];
    int max;
    
    for(int i=0;i<a;i++)
    {
       A[i] =rand() ;
    }
    print(A,a); //stampa a video l'array generato
   
    
    cout<<endl;
  
    t1=clock();
     
  if (a<=0)
        cout<<"Error: underflow! Il vettore di input e' vuoto!\nInserire un valore positivo per n!\n";
              else if(k<=0||k>a)
                  cout<<"Error: k deve avere un valore positivo, che sia minore o uguale ad n!\n\n";
              else
    
    for (int i=0;i<k;i++){
    HeapExtractMax (A,max,a,i); //chiama k volte HeapExtractMax per determinare i k numeri più grandi
    }
    t2=clock();
    
    
    timepast=t2-t1; //calcola il numero dei cicli di clock utilizzati dalla procedura HeapExtractMax
    
    
 if (a>0 && k>0 && k<=a){
    cout<<"\nI "<<k<<" numeri piu' grandi sono stati identificati in\n";
    cout<< timepast<< " cicli di clock.\n";
}
    

    system("Pause");
    return 0;
}

[alka]

Invito a leggere il Regolamento per conoscere tutte le norme da seguire nell'apertura di discussioni.

Ad esempio, qui manca il linguaggio nel titolo e la formattazione del codice sorgente pubblicato, che ho provveduto ad aggiungere io.

In futuro, provvedi tu.