Форум программистов [Powered by Invision Power Board]

Цитата

make_heap
function template
<algorithm>
template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

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

Make heap from range
Rearranges the elements in the range [first,last) in such a way that they form a heap. In order to rearrange these elements, the function performs comparisons using operator< for the first version, and comp for the second.

Internally, a heap is a tree where each node links to values not greater than its own value. In heaps generated by make_heap, the specific position of an element in the tree rather than being determined by memory-consuming links is determined by its absolute position in the sequence, with *first being always the highest value in the heap.

You can add or remove elements from a heap in logarithmic time by using the functions push_heap and pop_heap. These functions preserve the heap properties of the range passed to them.

Parameters
first, last
Random-Access iterators to the initial and final positions of the sequence to be transformed into a heap. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value
none

Цитата

push_heap
function template
<algorithm>
template <class RandomAccessIterator>
  void push_heap ( RandomAccessIterator first, RandomAccessIterator last );

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

Push element into heap range
Given a heap range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location in it.

A range can be made into a heap by calling function make_heap. Once created, its heap properties can be preserved by using push_heap and pop_heap respectively to add and remove values from it.

Parameters
first, last
Random-Access iterators to the initial and final positions of the new heap, including the pushed element. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value
none

Цитата

pop_heap
function template
<algorithm>
template <class RandomAccessIterator>
  void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );

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

Pop element from heap range
Rearranges the elements in the range [first,last) in such a way that the part considered a heap is shortened by one by removing its highest element.

The function actually moves the value at first to (last-1), and adjusts the values of the elements in the range [first,last-1) so that this part of the range retains the heap property (with its first element being the new highest value).

A range can be made into a heap by calling function make_heap. Once created, its heap properties can be preserved by using push_heap and pop_heap respectively to add and remove values from it.

Parameters
first, last
Random-Access iterators to the initial and final positions of the heap to be shrank by one. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value
none

Цитата

sort_heap
function template
<algorithm>
template <class RandomAccessIterator>
  void sort_heap ( RandomAccessIterator first, RandomAccessIterator last );

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

Sort elements of heap
Rearranges the elements in the heap range [first,last) in such a way that they form a sorted range. The comparisons are perfomed using operator< for the first version, and comp for the second.

The range loses its heap properties.

Parameters
first, last
Random-Access iterators to the initial and final positions of the heap range to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value
none

Цитата

reverse
function template
<algorithm>
template <class BidirectionalIterator>
  void reverse ( BidirectionalIterator first, BidirectionalIterator last);

Reverse range
Reverses the order of the elements in the range [first,last).

The behavior of this function template is equivalent to:
    template <class BidirectionalIterator>
  void reverse ( BidirectionalIterator first, BidirectionalIterator last)
{
  while ((first!=last)&&(first!=--last))
    swap (*first++,*last);
}

Parameters
first, last
Bidirectional iterators to the initial and final positions of the sequence to be reversed. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Return value
none

Код

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int myints[] = {10,20,30,5,15};
  vector<int> v(myints,myints+5);

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