push_heap

Синтаксис:

    #include <algorithm>
    void push_heap( random_access_iterator start, random_access_iterator end );
    void push_heap( random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp );

Функция push_heap() добавляет элемент (определенный как последний элемент перед концом) к куче (определенной как диапазон элементов между [start,end-1) ).

Если требуется повышенная точность, вводится упорядочивающая сравнивающая функция-объект cmp, которая используется вместо оператора < для сравнения элементов.

push_heap() работает за логарифмическое время.

Пример:

// Пример кучи
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main () {
  int myints[] = {10,20,30,5,15};
  vector<int> v(myints,myints+5);
  vector<int>::iterator it;
 
  make_heap (v.begin(),v.end());
  cout << "initial max heap   : " << v.front() << endl;
 
  pop_heap (v.begin(),v.end()); v.pop_back();
  cout << "max heap after pop : " << v.front() << endl;
 
  v.push_back(99); push_heap (v.begin(),v.end());
  cout << "max heap after push: " << v.front() << endl;
 
  sort_heap (v.begin(),v.end());
 
  cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
 
  cout << endl;
 
  return 0;
}

Вывод: initial max heap  : 30

max heap after pop : 20

max heap after push: 99

final sorted range : 5 10 15 20 99

Смотрите также: is_heap, make_heap, pop_heap, sort_heap