STL Veri Yapısı - Priority Queue

Giriş
Şu satırı dahil ederiz.

#include <queue>  

Priority Queue, Queue, Stack container adapter sınıfları olarak tabir edilirler.

Tanımlama

Sınıfın tanımı şöyle. Büyükten küçüğe doğru sıralama yapar.

namespace std {
  template <class T,
            class Container = vector<T>,
            class Compare = less<Container::value_type> >
  class priority_queue;
}

Yanlış Tanımlama

Comparator sınıf içinde yaratılacağı için, template parametresi olarak function'ın kendisi verilemez.

bool cmp (const int &a,const int &b){ return a > b; }
priority_queue<int, vector<int> , cmp > y;   //error

C++11 ile şöyle yapmak gerekir.

std::priority_queue<int, std::vector<int>, decltype(&cmp)> x(cmp);

Küçükten Büyüğe - Comparator
> karşılatırması yapan comparator kullanırız. Şöyle yaparız.

class mycomparator
{ 
  public:
    bool operator()(const Node *a, const Node *b) const
    {
      return (a->gscore) > (b->gscore);
    }
};

Şöyle tanımlarız.

std::priority_queue<Node*,std::vector<Node*>,mycomparator> q;

Küçükten Büyüğe - std::greater
Sınıfın kendi > operatörünü kullanırız. Şöyle yaparız.

bool operator>(Node a, Node b){
  ...
}

Şöyle tanımlarız.

std::priority_queue<point, std::vector<Node>, std::greater<Node>> q;

Büyükten Küçüğe - Comparator
< karşılatırması yapan comparator kullanırız. Şöyle yaparız.

class mycomparator
{ 
  public:
    bool operator()(const Node *a, const Node *b) const
    {
      return (a->gscore) < (b->gscore);
    }
};

Şöyle tanımlarız.

std::priority_queue<Node*,std::vector<Node*>,mycomparator> q;

Büyükten Küçüğe - std::less
Sadece sınıfın kendi < operatörünü kullanırız. Şöyle yaparız.

bool operator < (Node a, Node b){  ...
}

Lambda Comparator

Comparator olarak struct veya class kullanmak yerine istersek şöyle yaparız.

auto comp = [](int x, int y) { return x > y; };
std::priority_queue<int, std::vector<int>, decltype(comp)> q(comp);

Struct Template Comparator
Şöyle yaparız.

template<typename T>
struct comparator
{
  bool operator()(T a, T b)
  {
    if(a->freq>b->freq) {
      return true;
    }
    else{
        return false;
    } 
  }
};

Constructor

Sınıfın constructor imzası şöyle

explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );

Açıklaması ise şöyle

Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare. Calls std::make_heap(c.begin(), c.end(), comp). This is also the default constructor.

Default constructor
Sınıfımın < operatörü olduğunu varsayarsak şöyle yaparız.

std::priority_queue<MyClass> q;

empty metodu
Şöyle yaparız.

while (!q.empty()) {
  cout << q.top() << " ";
  q.pop();
}

push ve pop metodu
Bu metolarla priority_queue sınıfını doldururuz ve boşaltırız.

priority_queue<Event, vector<Event>, CompareEvent> eventList;

Event newEvent;
newEvent.name = eventName;
newEvent.time = time;
newEvent.pid = pid;

eventList.push(newEvent);
eventList.top();
eventList.pop();

top metodu
const reference döner.

Diğer Konular

1. Container'a Erişmek

Normalde mümkün değil ancak hack'leyerek yapılabilir. Örnekte std::priority_queue sınıfından kalıtan başka bir sınıf var. Yeni sınıf this->c ile container nesnesine erişebiliyor.

#include<iostream>
#include<queue>
using namespace std;
template<class type>
struct mypq :public priority_queue<type> {
    void clear(){
        this->c.clear();
    }
};

Eğer illaki elemanlara erişmemiz gerekiyorsa bir vector ile std::make_heap , std::push_heap , std::pop_heap metodlarını kullanılarak yapılabilir.

2. Heap Sort

Priority Queue her zaman en büyük elemanı almak için kullanılır. Kendi içinde heap sort yapar. Dolayısıyla top() metodu O(1) ile çalışır.

Binary heap veriyi kısmi olarak sıralı tutar. Eğer priority_queue sınıfı iterator metodları sunsaydı bile, veriyi sıralanmış bir şekilde dolaşmak mümkün değildi.

Java'daki PriorityQueue sınıfı iterator metodları sunuyor ancak elemanları dolaşma konusunda da uyarı da bulunuyor.

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).