Maradék az előző óráról: Képtömörítés változással
Elmélet: prioritási sorA prioritási sorban tárolt elemekhez tartozik egy kulcs, a prioritás. Hatékony (O(log N)) az alábbi műveletek elvégzése: beszúrás a sorba, a legkisebb (legnagyobb) prioritású elem kiolvasása illetve törlése. A prioritási sor egyik lehetséges megvalósítása a kupac adatszerkezetre épül, de ezen az órán nem foglalkozunk a megvalósítással, hanem a java és a c++ standard könyvtárát használjuk.
Vigyázat! A C++ és a Java esetében is szükség lehet összehasonlító operátor definiálására. Ezek az operátorok a különböző nyelvekben máshogy működnek. A két legfontosabb különbség - amit a nyelv specifikációjából ki kell derítenünk - a következő:
A lenti példákban a Java-ban háromkimenetű egész értékű összehasonlítást, míg a C++ kétkimenetű logikai értékű összehasonlítást használunk. PéldákEgészek rendezése prioritási sorral Java-banimport java.util.PriorityQueue; class pq1 { public static void main(String args[]) { PriorityQueue pq = new PriorityQueue<Integer>(); pq.add(12); pq.add(3); pq.add(-9); pq.add(2015); pq.add(42); while(!pq.isEmpty()) { System.out.print(pq.poll()+" "); } System.out.println(); } } Objektumok rendezése prioritási sorral Java-banimport java.util.PriorityQueue; class pq2 { static class Intervallum implements Comparable<Intervallum>{ int a, b; public Intervallum(int mya, int myb) { if(myb > mya) { a = mya; b = myb; } else { b = mya; a = myb; } } public int compareTo(Intervallum masik ){ int d = b-a; int dd = masik.b - masik.a; return d-dd; } public String toString() { return "["+a+";"+b+"]"; } } public static void main(String args[]) { PriorityQueue pq = new PriorityQueue<Intervallum>(); pq.add(new Intervallum(2,3)); pq.add(new Intervallum(2,20)); pq.add(new Intervallum(5,6)); pq.add(new Intervallum(-1,0)); pq.add(new Intervallum(10,100)); while(!pq.isEmpty()) { System.out.print(pq.poll()+" "); } System.out.println(); } } Egészek rendezése prioritási sorral C++-ban#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int, vector<int>, greater<int> > pq; pq.push(12); pq.push(3); pq.push(-9); pq.push(2015); pq.push(42); while(!pq.empty()) { cout << pq.top() << ' '; pq.pop(); } cout << endl; } Objektum rendezése prioritási sorral C++-ban#include <iostream> #include <queue> using namespace std; class Intervallum { public: int a,b; Intervallum(int mya, int myb) { if(myb > mya) { a = mya; b = myb; } else { b = mya; a = myb; } } }; struct Compare { bool operator() (const Intervallum x, const Intervallum y) const { return (x.b-x.a) > (y.b-y.a); //növekvő rendezéshez } }; int main() { priority_queue<Intervallum, vector<Intervallum>, Compare > pq; pq.push(Intervallum(2,3)); pq.push(Intervallum(2,20)); pq.push(Intervallum(-1,0)); pq.push(Intervallum(5,6)); pq.push(Intervallum(10,100)); while(!pq.empty()) { cout << '[' << pq.top().a << ';' << pq.top().b << ']' << ' '; pq.pop(); } cout << endl; } Feladat |