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.

 #include<algorithm> 

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

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

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

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

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:

bool comp(type a, type b) 

gdzie type jest typem obiektów przechowywanych w kolekcji. Jeżeli trzeci argument nie zostanie podany, do porównania używany jest operator < .

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

A to fragment kodu ilustrujący tę sytuację:

#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;
} 

   template <class RandomAccessIterator>
            void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );
 
   template <class RandomAccessIterator, class Compare>
            void pop_heap ( RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp );

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:

bool comp(type a, type b)

gdzie type jest typem obiektów przechowywanych w kolekcji. Jeżeli trzeci argument nie zostanie podany, do porównania uzywany jest operator < .

Poniższa ilustracja pokazuje działanie algorytmu pop_heap:

A to fragment kodu ilustrujący tę sytuację:

#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;
}

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: heap_pop_push.cpp