Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2015-2016‎ > ‎

7. alkalom

Maradék az előző óráról: Képtömörítés változással

Elmélet: prioritási sor

A 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.

 Java (alapértelmezett rendezés: min)  C++ (alapértelmezett rendezés: max)
 import java.util.PriorityQueue; #include <queue>
 PriorityQueue pq =   new PriorityQueue<Integer>();  priority_queue<int> pq;
 pq.add(12); pq.push(12);
 int x = pq.peak(); int x = pq.top();
 int y = pq.poll(); int y = pq.top();
 pq.pop();
 if( pq.isEmpty() ) {...} if( pq.empty() ) {...}
  
  

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ő:
  • operátor értéke (a számított érték típusa): logikai vagy egész típusú
  • operátor jelentése: <= és > vagy <, = és > megkülönböztetésére használható
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ák

Egészek rendezése prioritási sorral Java-ban

import 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-ban

import 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