Heap

julchatt

Hallo Leute,

ich komme mit der Implementierung der folgenden Methode nicht klar, kann mir jemand helfen, es geht um Prioritätswarteschlange als Heap

void PriorityQueue::Insert(const PQElement& anew){}

class PriorityQueue {
          int n;              // aktuelle Laenge
          int length;         // Gesamtlaenge=Aufnahmekapazitaet
          PQelement *a;       // fuer das Feld

    public:
          int l;

          void PriorityQueue(int l=1000){
            int length = l;
            int n = 0;
            int a = new PQElement[length];
          }

          PQElement& Maximum(void) const; 

          PQElement Extract_Max(void);

          void DownHeap(int i, int n, int a[n]);

          void Insert(const PQElement& anew);//Liefert a[1].

          //liefert das bzw. eines der Elemente mit der höchsten Priorität
          void Maximum();

          void ExtractMax();

}

drakon

Wo genau ist das Problem?
Weisst du wie es theoretisch geht?

julchatt

theoretisch weiß ich es, aber mit der Umsetzung in c++ hapert es ziemlich stark...

also diese insert Methode muss ein neues Element am Ende der Schlange einfügen, dabei muss sie per Random() die Priorität zugewiesen werden und anschließend per upHeap die Heapeigenschaft wieder herstellen...und die Random Klasse ist hier...

Random::Random(int r = -1) // Defaultparameter
{
	max_range = r;
	fill_mask = 0;
	fill_bits = 0;
	/* determine no. of bits required */
	if (max_range > RAND_MAX) {
		int req_padding = (max_range / RAND_MAX);
		//cout << "Required padding is: " << req_padding << endl;
		int cur_padding = 1;
		while (cur_padding < req_padding) {
			cur_padding = cur_padding << 1;
			fill_mask = fill_mask << 1;
			fill_mask += 1;
			fill_bits++;
		}
	}
	//cout << "No. of fill bits is: " << fill_bits << endl;
	//cout << "Fill mask is: " << fill_mask << endl;
	//srand(clock());
	srand (12);
}

Random::~Random()
{
}

int Random::give()
{
	int value = rand();
	int sec_value = rand();

	for (int i = 1; i <= fill_bits; i++) {
		value = value << 1;
	}
	value += (sec_value &&  fill_mask);
	return (value % max_range);
}