OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Kolejka priorytetowa to ADT zawierający elementy z kluczami (priorytetami), która pozwala na przeprowadzenie następujących operacji:
Kolejki priorytetowe często używają wewnętrznie kopca. Wtedy tablicę zamienia się w kopiec w czasie O(n), a wstawianie i usuwanie elementów zajmuje czas O(log n). Alternatywą są drzewa binarne samobalansujące się.
// https://en.cppreference.com/w/cpp/container/priority_queue #include <queue> // W STL kolejka priorytetowa jest zbudowana na bazie std::vector, // inna możliwość to std::deque. // Jest to otoczka do zarządzania wewnętrznym kopcem. // Domyślnie w stałym czasie mamy dostęp do elementu największego. // Wstawianie i usuwanie elementów z kolejki zajmuje czas O(log n). // Można dostarczyć funkcję porównującą, która będzie użyta do ustalenia // priorytetów elementów, domyślnie jest to std::less. // Przykład użycia kolejki priorytetowej. //std::priority_queue<int> pq; // domyślnie std::vector //std::priority_queue<int, std::deque<int> > pq; //std::priority_queue<int, std::vector<int>, std::greater<int> > pq;
// Własna funkcja porównująca.
auto cmp = [] (int left, int right) { return left > right; };
std::priority_queue<int, std::vector<int>, decltype(cmp) > pq(cmp);
// https://en.cppreference.com/w/cpp/language/decltype
// decltype() is useful when declaring types that are difficult
// or impossible to declare using standard notation, like lambda-related
// types or types that depend on template parameters.
// Wstawianie do kolejki par (priority, item) [jak w Pythonie].
auto cmp = [] (std::pair<int,float> left, std::pair<int,float> right) {
return left.first < right.first; };
std::priority_queue< std::pair<int,float>,
std::vector< std::pair<int,float> >,
decltype(cmp) > pq(cmp);
std::priority_queue<int> pq;
assert( pq.empty() );
for (auto item : {1, 5, 4, 2, 3})
pq.push(item); // wstawienie do kolejki
assert( pq.size() == 5 );
// Pobranie z kolejki elementu i wypisanie go.
std::cout << pq.top() << std::endl; // wypisuje, ale nie zdejmuje!
pq.pop(); // usuwa z kolejki, ale nie zwraca
assert( pq.size() == 4 );
while (!pq.empty()) {
std::cout << pq.top() << std::endl;
pq.pop();
}
// https://en.cppreference.com/w/cpp/algorithm/make_heap // Constructs a max heap in the range [first, last). template < class RandomIt > void make_heap( RandomIt first, RandomIt last ); template < class RandomIt > void make_heap( RandomIt first, RandomIt last, Compare comp );
// https://en.cppreference.com/w/cpp/algorithm/push_heap // A new element can be added using std::push_heap(). // Element na pozycji last-1 jest wstawiany do kopca [first, last-1). template < class RandomIt > void push_heap( RandomIt first, RandomIt last ); template < class RandomIt > void push_heap( RandomIt first, RandomIt last, Compare comp );
// https://en.cppreference.com/w/cpp/algorithm/pop_heap // The first element can be removed using std::pop_heap(). // Element z pozycji first jest zamieniany z last-1, a następnie // zakres [first, last-1) jest zamieniany na kopiec. template < class RandomIt > void pop_heap( RandomIt first, RandomIt last ); template < class RandomIt > void pop_heap( RandomIt first, RandomIt last, Compare comp );
// https://en.cppreference.com/w/cpp/algorithm/sort_heap // Converts the max heap [first, last) into a sorted range in ascending order. // The resulting range no longer has the heap property. template < class RandomIt > void sort_heap( RandomIt first, RandomIt last ); template < class RandomIt > void sort_heap( RandomIt first, RandomIt last, Compare comp );
// Sortowanie przez kopcowanie, złożoność O(n log n).
std::vector<int> v = {3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end()); // tworzenie kopca
std::sort_heap(v.begin(), v.end()); // wyjmowanie elementów największych
Przygotować implementację realizującą ADT PRIORITY QUEUE na bazie std::vector i kopca z STL. Wydajność: wstawianie O(log n), usuwanie O(log n), odczyt największego O(1).
#include <vector>
#include <algorithm> // make_heap, push_heap, pop_heap
template <typename T>
class MyPriorityQueue {
std::vector<T> lst; // działa domyślny konstruktor dla std::vector
public:
MyPriorityQueue(std::size_t s=10) { lst.reserve(s); } // default constructor
~MyPriorityQueue() { lst.clear(); }
MyPriorityQueue(const MyPriorityQueue& other); // copy constructor
MyPriorityQueue(MyPriorityQueue&& other); // move constructor
MyPriorityQueue& operator=(const MyPriorityQueue& other); // copy assignment operator, return *this
MyPriorityQueue& operator=(MyPriorityQueue&& other); // move assignment operator, return *this
bool empty() const { return lst.empty(); }
std::size_t size() const { return lst.size(); } // liczba elementów w kolejce
void push(const T& item) { // dodanie do kolejki
lst.push_back(item);
std::push_heap(lst.begin(), lst.end());
}
void push(T&& item) { // dodanie do kolejki
lst.push_back(std::move(item));
std::push_heap(lst.begin(), lst.end());
}
T& top() { return lst.front(); } // zwraca element największy, nie usuwa
void pop() { // usuwa element największy
std::pop_heap(lst.begin(), lst.end());
lst.pop_back();
}
void clear() { lst.clear(); } // czyszczenie listy z elementów
void display(); // nie oczekujemy jakiegoś uporządkowania elementów
};
Przygotować implementację realizującą ADT PRIORITY QUEUE nie korzystającą z kopca z STL, tylko własnych funkcji. Wydajność: wstawianie O(log n), usuwanie O(log n), odczyt największego O(1).
Przygotować prostą implementację realizującą ADT PRIORITY QUEUE na bazie listy powiązanej pojedynczo. Lista jest stale uporządkowana, a największy element znajduje się na początku listy. Można wykorzystać klasę SingleList lub std::forward_list. Wydajność: wstawianie O(n), usuwanie O(1), odczyt największego O(1).
Przygotować prostą implementację realizującą ADT PRIORITY QUEUE na bazie tablicy. Tablica nie jest uporządkowana. Wstawiamy nowy element na koniec tablicy. Przy usuwaniu elementu największego znajdujemy jego indeks, zamieniamy go miejscami z ostatnim elementem i skracamy tablicę jak dla stosu. Wydajność: wstawianie O(1), usuwanie O(n), odczyt największego O(n).