obsluga kolejki priorytetowej na wektorze uporządkowanym kopcowo - zła obsługa kopca

0

Witam serdecznie,

miałem za zadanie napisać program, w którym zaimplementuje klasę i metody klas do obsługi kolejki priorytetowej w wersji na wektorze uporządkowanym kopcowo.
wykonując program dla 10 liczb wygenerowanych losowo, otrzymuję taki rezultat przy "ściąganiu" wartości z kopca metodą get_max():
user image

Jak widać, za drugim razem ściągana wartość się powtarza (return liczby 262 a następnie zamiana z korzeniem i skrócenie wektora. wartość 100 ginie). Tak jest zawsze - druga wartość zdjęta get_maxem() się powtarza. Nie wszystkie wartości są obsłużone.

wyciąłem kod, temat można zamknąć :)

0

sugestia: wydaje mi się, że metoda get_max() jest zła

0

Wrzuć cały i kompilujący się kod.

0

main.cpp

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include <cstring>
#include "BIBLIOTECZKA.h"

#define LINIA() cout<<"\n"; for(int z=0; z<=79; z++) cout<<"_"; cout<<"\n";



main()
{
	  char znak;
	  
	  
	  
	  priorityQueue kolejka;
	  pq_heap kopiec;

	  vector<int> losowe;	
	  losuj(losowe,10);
	  
	  clock_t t_start;
	  

	  
	  do {
	  		LINIA();
		    cout<<"\t\tABSTRAKCYJNE TYPY DANYCH\n\n\tProgram testujacy implementacje kolejki\n\tpriorytetowej w wersji zwyklej oraz\n\ttablicy uporzadkowanej kopcowo.\n";
	  		cout<<"\n\t\tWYBIERZ TEST:\n\n";
	  		cout<<"\t1\t\ttest obslugi zwyklej kolejki priorytetowej\n\t2\t\ttest obslugi kolejki uporzadkowanej kopcowo\n\n\t3\t\ttest wydajnosci dla n=100000\n\n\tq / Q\t\twyjscie z programu\n";
			LINIA();
			cout<<"wybor: ";
			znak=getchar();
			
/* **************************************************************** */
/* **************************************************************** */
			if(znak=='1')
			{
				for(int z=0; z<=9; z++)
					kolejka.wstaw(losowe[z]);
				cout<<"\nkolejka 10 liczb wygenerowanych losowo:\n\n";
				kolejka.wypisz(); cout<<"\n\n";
				for(int z=0; z<=9; z++)
				{
						cout<<"<< obsluzono "<<kolejka.get_max()<<" >>\n\n\t";
						kolejka.wypisz(); cout<<"\n\n";
				} kolejka.get_max();
			
				break;
			}
			
/* **************************************************************** */
/* **************************************************************** */

			if(znak=='2')
			{
				for(int i=0; i<=9; i++)
					kopiec.wstaw(losowe[i]);
				cout<<"\nkopiec 10 liczb wygenerowanych losowo:\n\n";
				kopiec.wypisz(); 	cout<<"\n\n";
				for(int i=0; i<9; i++)
				{
					cout<<"<< obsluzono "<<kopiec.get_max()<<" >>\n\n\t";
					kopiec.wypisz(); cout<<"\n\n";	
				} cout<<"<< obsluzono "<<kopiec.get_max()<<" >>\n\n"; kopiec.get_max();
				break;
			}
			
			
/* **************************************************************** */
/* **************************************************************** */

			if(znak=='3')
			{
				    cout<<"\nTestowanie wydajnosci... prosze uzbroic sie w cierpliwosc :)\n\n\tTest polega na ustawieniu w kolejce 100000 liczb typu integer\n\ta nastepnie obsluzeniu ich zgodnie z zasada kolejki priorytetowej.\n\n";
					losuj(losowe, 100000);
					
					t_start=clock();
					for(int z=0; z<=99999; z++)
							kolejka.wstaw(losowe[z]);
					for(int z=0; z<=99999; z++)
							cout<<kolejka.get_max()<<" ";
					cout<<"zwykla kolejka priorytetowa:\t\t"<<((float)(clock()-t_start)/CLOCKS_PER_SEC)<<"\n";
					
					t_start=clock();
					for(int z=0; z<=99999; z++)
							kopiec.wstaw(losowe[z]);
					for(int z=0; z<99999; z++)
							cout<<kopiec.get_max()<<" ";
					cout<<"kolejka priorytetowa na kopcu:\t\t"<<((float)(clock()-t_start)/CLOCKS_PER_SEC)<<"\n";
					
					break;
			}
			
	  } while (znak!='q');
	  

	  
	  cout<<"\n\twykonano.";
	  
	  
   
      getchar(); getchar();
}

funcyjnie.cpp

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<sstream>
#include<vector>
#include<math.h>
#include<algorithm>
#include "biblioteczka.h"

using namespace std;

void losuj(vector<int> &wektor, int ile)
{
		 int los;

         for(int i=0; i<ile; i++)
         {
         		los = rand()%300;
         		wektor.push_back(los); 
         }
}

priorityQueue::priorityQueue()
{
 
}

priorityQueue::~priorityQueue()
{
   		pq.clear();
}

void priorityQueue::wstaw(int x)
{
           pq.push_back(x);

}

bool priorityQueue::empty()
{
	 if (pq.size()<1) return true; 
	 if (pq.size()>=1) return false; 
}

int priorityQueue::get_max()
{
	    if (!pq.empty())
	    {
	   			int max=0, kluczmax=0;
				for(int i=0; i<= pq.size()-1; i++)
						if (pq[i]>max) { max=pq[i]; kluczmax=i; }
				pq[kluczmax] = pq[pq.size()-1];
				pq.resize(pq.size()-1);
				return max;
		} else 
		{
				cout<<"\tkolejka pusta\n";
				
		}
}

void priorityQueue::wypisz()
{
		int i;
		if(!pq.empty())
			for(i=0; i<=pq.size()-1; i++)
			{
					cout<<pq[i]<<"\t";
			}
}

pq_heap::pq_heap()
{
	
}

pq_heap::~pq_heap()
{
	//heap.clear();
}

void pq_heap::wstaw(int x)
{
		heap.push_back(x);
		fixUP(heap.size()-1);		

}

bool pq_heap::empty()
{
	 if (heap.size()<1) return true; 
	 if (heap.size()>=1) return false; 
}

int pq_heap::get_max()
{
	    int max=heap[0];
		if (!heap.empty())
	    {
				swap(heap[0], heap[heap.size()-1]);
				
				heap.resize(heap.size()-1);
				
				fixDown(0);
				
				return max;
		} 
		else 
		{
				cout<<"\tkopiec pusty\n"<<endl;
				
		}
}

void pq_heap::fixUP(int k)
						   
{
	if(k==0)
		return;
	if(heap[parent(k)] < heap[k])
	{
			int temp = heap[parent(k)];
			heap[parent(k)]=heap[k];
			heap[k]=temp;
			fixUP(parent(k));
	}
	
	
}

void pq_heap::fixDown(int k)
{
	while(left(k)<=heap.size()-1)
	{
		int j = left(k);
		if(heap[left(k)]<heap[right(k)])
				j = right(k);
		if((heap[k] < heap[left(k)]) || (heap[k] < heap[right(k)]))
		{
				swap(heap[k], heap[j]);
				k=left(k);
		} else break;
	}
	for(int j=heap.size()-1; j>0; j--)
			fixUP(j);
}
	
	


void pq_heap::wypisz()
{
		int i;
		for(i=0; i<=heap.size()-1; i++)
		{
				cout<<heap[i]<<"\t";
		}
}


biblioteczka.h

#ifndef BIBLIOTECZKA_h
#define BIBLIOTECZKA_h

using namespace std;

void losuj(vector<int> &wektor, int ile);

class priorityQueue
{
	private:
 	   vector<int> pq;
	   
	public:
   	   priorityQueue();
      ~priorityQueue();
       void wstaw(int x);
       int get_max();
       bool empty();
       void wypisz();
       
};

class pq_heap
{
	private:
 	   vector<int> heap;
 	   
 	   
 	   int left(int i) { return 2*i+1; }
 	   int parent(int i) {return (i-1)/2; }
 	   int right(int i) {return 2*i+2; }
	   
	public:
   	   pq_heap();
      ~pq_heap();
       void fixUP(int);
       void fixDown(int);
       void wstaw(int x);
       int get_max();
       bool empty();
       void wypisz();
       
};

#endif
0

Uwagi: rozrysowując kopiec pierwotny (liczby wylosowane, jeszcze bez ściągania największej wartości funkcją get_max()) w postać drzewa, mogę stwierdzić, że kopiec tworzony jest poprawnie. Przy ściąganiu liczb get_max'em pojawia się tendencja: obsługuje jedną liczbę (znajduje max, to jest pierwszy element), zamieniam go z ostatnim, zmniejszam rozmiar wektora przez co pozbywam się obsłużonej liczby, naprawiam kopiec FixDown'em. Drugi przebieg: zamiast zdjęcia pierwszej liczby z kopca (na rysunku 262) skracany jest jedynie rozmiar wektora. Obsługa największej (262) następuje dopiero w trzecim przebiegu. Po paru przebiegach występuje identyczny paradoks.

1

O Panie, kto to Panu tak... ;)

  1. W funkcji
fixDown 

sprawdzasz, czy lewy syn mieści się w tablicy. Spoko, ale nie sprawdzasz, czy prawy syn też się mieści, przez co wylatujesz poza zakres.
2. Wszędzie gdzie robisz

heap.size() - 1

masz istotny błąd — rozmiar jest liczbą nieujemną, więc jak odejmiesz jedynkę, to przekręcisz zmienną. Używaj porównania „mniejszy” zamiast „mniejszy lub równy” i nie odejmuj jedynki.
3. W kodzie

 for (int i = 0; i<9; i++)
			{
				cout << "<< obsluzono " << kopiec.get_max() << " >>\n\n\t";
				kopiec.wypisz(); cout << "\n\n";
			} cout << "<< obsluzono " << kopiec.get_max() << " >>\n\n"; kopiec.get_max();
			break;

Masz o jedno wywołanie

 get_max()

za dużo, przez co znowu wylatujesz poza zakres.

0
Afish napisał(a):
  1. W kodzie
 for (int i = 0; i<9; i++)
			{
				cout << "<< obsluzono " << kopiec.get_max() << " >>\n\n\t";
				kopiec.wypisz(); cout << "\n\n";
			} cout << "<< obsluzono " << kopiec.get_max() << " >>\n\n"; kopiec.get_max();
			break;

Masz o jedno wywołanie

 get_max()

za dużo, przez co znowu wylatujesz poza zakres.

ostatni get_max jest po to, żeby instrukcja sprawdzająca, czy kopiec jest pusty, wypisała magiczne "kopiec pusty." w ostatnim kroku.

z resztą jeszcze walczę. dzięki za wskazówki :)

0

No może i taki był cel, ale kod jest inny:

int pq_heap::get_max()
{
        int max=heap[0];
        if (!heap.empty())
        {
                swap(heap[0], heap[heap.size()-1]);
 
                heap.resize(heap.size()-1);
 
                fixDown(0);
 
                return max;
        } 
        else 
        {
                cout<<"\tkopiec pusty\n"<<endl;
 
        }
} 

Najpierw pobierasz element i nie patrzysz, czy ten element istnieje, więc w przypadku pustego kopca będzie problem.

0

To teraz jeszcze jedno pytanie, związane z dalszą częścią zadania: jak to przerobić, żeby obsługiwało tablice znaków? Tj. zbudować kopiec zgodny z ideą kolejki priorytetowej, który będzie przechowywał łańcuchy znaków. A potem to jeszcze sortował, ale pozostańmy przy samej konstrukcji - jakieś pomysły?

1

vector<string> pq; - a dalej zmieniać tam gdzie kompilator krzyczy.

0
_13th_Dragon napisał(a):

vector<string> pq; - a dalej zmieniać tam gdzie kompilator krzyczy.

Zbawco! :D udało się. A teraz nieco trudniej: tak samo, tylko na tablicy znaków.. bez masy przebudowywania da się coś osiągnąć? bo rozumiem, że takie porównania jak na wektorze string są dla tablic niemożliwe i musiałbym iterować każde słowo, i...

0

Nie rozumiem, co znaczy tablica znaków? Czy nie możesz użyć string jako tablicy znaków?

0

niestety, nie wszystko w życiu ma sens, na przykład treść zadania, które mam zrobić. mam użyć dynamicznej tablicy char. a potem jeszcze tablicy string (nie wektora). sortowanie na 3 typach danych. widzisz, w jakim jestem bagnie. pomożesz?

0

Zrób z tego klasę i po sprawie.

0

to już jest klasą:


pq_heap::pq_heap()
{
	
}

pq_heap::~pq_heap()
{
	
}

void pq_heap::wstaw(string x)
{
		heap.push_back(x);
		fixUP(heap.size()-1);		

}

bool pq_heap::empty()
{
	 if (heap.size()<1) return true; 
	 if (heap.size()>=1) return false; 
}

string pq_heap::get_max()
{
	    string max=heap[0];
		if (!heap.empty())
	    {
				swap(heap[0], heap[heap.size()-1]);
				
				heap.resize(heap.size()-1);
				
				fixDown(0);
				
				return max;
		} 
		else 
		{
				cout<<"\tkopiec pusty\n"<<endl;
				
		}
}

void pq_heap::fixUP(int k)
						   
{
	if(k==0)
		return;
	if(heap[parent(k)] < heap[k])
	{
			string temp = heap[parent(k)];
			heap[parent(k)]=heap[k];
			heap[k]=temp;
			fixUP(parent(k));
	}
	
	
}

void pq_heap::fixDown(int k)
{
	while((left(k)<heap.size()) && (right(k)<heap.size()))
	{
		int j = left(k);
		if(heap[left(k)]<heap[right(k)])
				j = right(k);
		if((heap[k] < heap[left(k)]) || (heap[k] < heap[right(k)]))
		{
				swap(heap[k], heap[j]);
				k=left(k);
		} else break;
	}
	for(int j=heap.size()-1; j>0; j--)
			fixUP(j);
}
	
	


void pq_heap::wypisz()
{
		int i;
		for(i=0; i<heap.size(); i++)
		{
				cout<<heap[i]<<" ";
		}
}



void heapsortuj(vector<string> &wektor)
{
		pq_heap kopiectemp;
		vector<string> temp;
		string liczba;
	    for(int i=0; i<wektor.size(); i++)
		     kopiectemp.wstaw(wektor[i]);
		     
		cout<<"Zbudowano kopiec. Kopiec wyglada nastepujaco: \n\n";
		kopiectemp.wypisz(); cout<<endl<<endl;;
		
		for(int i=0; i<wektor.size(); i++)
		{
			 liczba = kopiectemp.get_max();
		     temp.push_back(liczba);
		}
		
		copy(temp.begin(), temp.end(), wektor.begin());
		
		
}
 

mam wrażenie, że potrzeba drastycznych zmian, jednak tak jestem otumaniony nadmiarem obowiązków, iż nic wielkiego nie wymyślę bez czynnika zapalającego, jakim będzie kilka konkretnych wskazówek. nie mam czasu do stracenia, więc proszę, błagam o słowa mądrości, mędrcy.

1

Napisz klasę podobną do string w której użyjesz dynamicznej tablicy char.

0
_13th_Dragon napisał(a):

Napisz klasę podobną do string w której użyjesz dynamicznej tablicy char.

pierwszy problem z tym rozwiązaniem:

 void pq_heap::wstaw(char x[])
{
		heap.push_back(x);
                /*
                        push_back to metoda wektora, jak osiągnąć to samo dla tablicy znaków?
                */
		fixUP(heap.size()-1);		

}

user image

1

char x[] - nie jest klasą.

0

coraz bliżej, jednak napotykam problem - jak by tu przekopiować wektor stringów do tablicy charów? znalazłem taki myk, ale to jeszcze nie to

user image

0

uporałem się z tym, proszę o zamknięcie albo usunięcie tematu. kod wycięty, gdyż wolałbym aby mój wykładowca nie dostał od kogoś mojego plagiatu :D sam znalazłem siebie pod drugim linkiem google zadając krótkie pytanie o heapsort, więc... dzięki za pomoc :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1