Różnice

Różnice między wybraną wersją a wersją aktualną.

--- push_heap_pop_heap [2009/04/10 18:34]
marszaaljr
+++ push_heap_pop_heap [2009/04/10 20:23] (aktualna)
marszaaljr
@@ Linia 1: / Linia 1: @@
 ======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

Różnice

Narzędzia strony