Imprimă pagina

Titlul: heap
Scris de: Adrian Craciun din Aprilie 06, 2011, 09:58:32

cum sa fac un heap care sa aiba sortate elementele crescator (cu STL)?
am incercat asa dar vad ca nu merge (sau debuggerul face figuri)
priority_queue< int, deque<int>, less<int> > t;

si inca o intrebare... cum introduc un element in heap daca lucrez cu structuri
(adica avem un struct nod { int a; int b } pe care este definit heapul) fara sa folosesc o variabila a de tip nod ?

ms :D

Titlul: Răspuns: heap
Scris de: Lepadat Mihai-Alexandru din Aprilie 06, 2011, 10:11:10

Cod:

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]<cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

Ce motive ai sa nu folosesti o variabila de tip nod?

Titlul: Răspuns: heap
Scris de: Adrian Craciun din Aprilie 06, 2011, 10:18:58

Cod:

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]<cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

asta stiam si eu sa fac.
scuze nu m-am exprimat bine am vrut sa zic folosind o functie de tipul greater<int>, less<int> etc. care sunt incluse in STL
(adica fara a ma complica cu un cmp :) )

Ce motive ai sa nu folosesti o variabila de tip nod?
Pai fiindca folosind o variabila in plus scrii mai multe linii de cod si te complici. (adica orice plus e binevenit, asa-i ? :D )

Titlul: Răspuns: heap
Scris de: Lepadat Mihai-Alexandru din Aprilie 06, 2011, 10:30:03

Ai putea folosi pair<> daca ai doar 2 variabile in structura si poti face push cu make_pair. Altcumva nu cred ca ai cum, cel putin eu nu stiu. Cat despre heap, nici acolo n-am alta idee, da' nu vad un mare efort sa faci cmp-ul, oricum face STL-ul destule. :D

Titlul: Răspuns: heap
Scris de: Mircea Dima din Aprilie 06, 2011, 12:31:52

Citat din mesajul lui: Adrian Craciun din Aprilie 06, 2011, 09:58:32

La primul punct, cred ca asta e ceea ce vrei:

Cod:

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

priority_queue<int, vector<int>, greater<int> > Q;

int main ()
{
    Q.push (3);
    Q.push (8);
    Q.push (7);

    while (!Q.empty ())
    {
	printf ("%d ", Q.top ());
	Q.pop ();
    }

    return 0;
}

Iar la a 2a, poti sa faci un constructor in structura si apoi sa ii spui Q.push (nod (1, 2));
Sau, mai simplu: Q.push ((nod) {1, 2}); (fara sa mai scrii constructor)

Titlul: Răspuns: heap
Scris de: Adrian Craciun din Aprilie 06, 2011, 13:10:01

ms ... asta cautam :D

Titlul: Răspuns: heap
Scris de: Pripoae Teodor Anton din Aprilie 09, 2011, 12:28:12

Faci cast.

Cod:

Q.push((nod){a,b});

Titlul: Răspuns: heap
Scris de: Adrian Craciun din Mai 02, 2011, 11:34:43

mai am o intrebare, cum declar un min-heap (ordonarea trebuie sa fie dupa primul element) de perechi ( pair <int, int> ) folosind priority_queue?
nu doresc variante alternative ca alea cam stiu si eu sa le fac :)

Titlul: Răspuns: heap
Scris de: Mihai-Alexandru Dusmanu din Mai 02, 2011, 12:00:39

pai, ceva de genu

Cod:

priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > H;

In cazul in care first-urile a doua pair-uri sunt egale, le tine si crescator dupa a second-uri

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Adrian Craciun din Aprilie 06, 2011, 09:58:32