zpr c++ quick reference

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
======push_heap i pop_heap - opis algorytmów======
Algorytmy push_heap i pop_heap służą do operacji na kolekcjach danych, w których elementy ustawione są w strukturze kopca (stogu). Algorytm push_heap dodaje nowy element do kolekcji, a algorytm pop_heap zdejmuje element ze szczytu kopca. Struktura kopca po zastosowaniu tych algorytmów pozostaje niezachwiana.

===== Nagłówek =====
	
<code cpp> #include<algorithm> </code>

Aby korzystać z algorytmów push_heap i pop_heap musimy dodać plik nagłówkowy <algorithm>. 

===== Struktura kopca =====

Użycie algorytmów push_heap i pop_heap ma sens jedynie wtedy, gdy kolekcja danych przechowuje elementy w strukturze kopca. Aby uzyskać strukturę kopca wykorzystujemy algorytm make_heap. Przykłady użycia i jego opis można znaleźć w tym pliku: {{:make_heap1.cpp|}} 

{{:kopiec.gif|}}

Na rysunku została przedstawiona kolekcja danych z elementami uporządkowanymi w kopiec. Kolorem czerwonym oznaczono indeksy tablicy. Kopiec sprawia, że na pierwszej pozycji znajduje się największy element (element tablicy o indeksie 0). Każde następne elementy są indeksowane według reguły:
              * jeśli rodzic ma indeks n to jego dzieci maja indeksy 2n+1 i 2n+2

===== push_heap - konstrukcja =====
<code cpp>
template <class RandomAccessIterator>
            void push_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
            void push_heap ( RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp );</code>

===== push_heap - argumenty =====
Iteratory last i first są iteratorami kolekcji danych i wskazują pewien zakres. Pierwsze elementy
w tym zakresie powinny być w postaci kopca, a ostatni element zakresu (pozycja last-1) powinien
być elementem, który chcemy dodać do kopca. Po wykonaniu algorytmu, element zostanie dodany na
właściwą pozycje tak, aby struktura kopca została zachowana. 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 używany jest operator < .

===== push_heap - zastosowanie =====
Poniższa ilustracja przedstawia, co się dzieje podczas użycia funkcji push_heap:

{{:kopiec_push.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};
    vector<int> wektor(liczby, liczby+5);

    make_heap(wektor.begin(),wektor.end());

    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //23 17 1 5 8

    wektor.push_back(80);
    cout<<endl;

    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //23 17 1 5 8 80

    push_heap(wektor.begin(),wektor.end());
    cout<<endl;

    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //80 17 23 5 8 1

    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>

===== Więcej przykładów... =====

Więcej przykładów, w tym także na wywołanie algorytmów pop_heap i push_heap z funkcją porównującą w argumencie, można znaleźć w tym pliku: {{:stl_algorytmy:stl_algorytmy:heap_pop_push.cpp|}}
zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
