Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
push_heap_pop_heap [2009/04/10 19:49] marszaaljr |
push_heap_pop_heap [2009/04/10 20:14] marszaaljr |
||
---|---|---|---|
Linia 19: | Linia 19: | ||
===== push_heap - konstrukcja ===== | ===== push_heap - konstrukcja ===== | ||
<code cpp> | <code cpp> | ||
- | template <class RandomAccessIterator> | + | template <class RandomAccessIterator> |
void push_heap ( RandomAccessIterator first, RandomAccessIterator last ); | void push_heap ( RandomAccessIterator first, RandomAccessIterator last ); | ||
- | template <class RandomAccessIterator, class Compare> | + | template <class RandomAccessIterator, class Compare> |
void push_heap ( RandomAccessIterator first, RandomAccessIterator last, | void push_heap ( RandomAccessIterator first, RandomAccessIterator last, | ||
Compare comp );</code> | Compare comp );</code> | ||
Linia 77: | Linia 77: | ||
return 0; | return 0; | ||
} | } | ||
+ | </code> | ||
+ | |||
+ | ===== pop_heap - konstrukcja ===== | ||
+ | |||
+ | <code cpp> | ||
+ | template <class RandomAccessIterator> | ||
+ | void pop_heap ( RandomAccessIterator first, RandomAccessIterator last ); | ||
+ | |||
+ | template <class RandomAccessIterator, class Compare> | ||
+ | void pop_heap ( RandomAccessIterator first, RandomAccessIterator last, | ||
+ | Compare comp ); | ||
+ | </code> | ||
+ | |||
+ | ===== pop_heap - argumenty ===== | ||
+ | |||
+ | Algorytm pop_heap zdejmuje element ze szczytu kopca. Pierwszy argument, to iterator wskazujący na początek kolekcji danych w postaci kopca, włącznie z elementem do usunięcia. Drugi argument, to iterator wskazujacy na koniec kolekcji. Po użyciu algorytmu, element usuwany jest umieszczany na pozycji last-1. Trzeci, opcjonalny argument, to funkcja, według której określony jest porządek kopca (relacja rozstrzygająca, który element jest "większy"). Funkcja musi być postaci: | ||
+ | <code cpp> | ||
+ | bool comp(type a, type b) | ||
+ | </code> | ||
+ | gdzie //type// jest typem obiektów przechowywanych w kolekcji. Jeżeli trzeci argument | ||
+ | nie zostanie podany, do porównania uzywany jest operator < . | ||
+ | |||
+ | ===== pop_heap - zastosowanie ===== | ||
+ | |||
+ | Poniższa ilustracja pokazuje działanie algorytmu pop_heap: | ||
+ | |||
+ | {{:kopiec_pop.gif|}} | ||
+ | |||
+ | A to fragment kodu ilustrujący tę sytuację: | ||
+ | |||
+ | <code cpp> | ||
+ | #include <vector> | ||
+ | #include <algorithm> | ||
+ | #include <iostream> | ||
+ | using namespace std; | ||
+ | |||
+ | int main(){ | ||
+ | | ||
+ | int liczby[]={1,5,23,17,8,99}; | ||
+ | vector<int> wektor(liczby, liczby+6); | ||
+ | | ||
+ | make_heap(wektor.begin(),wektor.end()); | ||
+ | for(int i=0;i<wektor.size();i++) | ||
+ | cout<<wektor[i]<<" "; | ||
+ | // 99 17 23 5 8 1 | ||
+ | | ||
+ | pop_heap(wektor.begin(),wektor.end()); | ||
+ | cout<<endl; | ||
+ | | ||
+ | for(int i=0;i<wektor.size();i++) | ||
+ | cout<<wektor[i]<<" "; | ||
+ | //23 17 1 5 8 99 | ||
+ | | ||
+ | wektor.pop_back(); | ||
+ | cout<<endl; | ||
+ | | ||
+ | for(int i=0;i<wektor.size();i++) | ||
+ | cout<<wektor[i]<<" "; | ||
+ | //23 17 1 5 8 | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | |||
</code> | </code> |