heap

[•deneo]

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

[•skull]

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?

[•deneo]

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 ?   )

[•skull]

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. 

[•blasterz]

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

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)

[•deneo]

ms ... asta cautam 

[•toni2007]

Faci cast.

Cod:

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

[•deneo]

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

[•dushmi]

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