Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
push_heap_pop_heap [2009/04/10 18:34] marszaaljr |
push_heap_pop_heap [2009/04/10 19:58] marszaaljr |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
======push_heap i pop_heap - opis algorytmów====== | ======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. | 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 < . |