0123456789 Initial contents of а:

20 50 40 60 80 10 30 70 25 45 After random shuffle(а, a+10):

80 10 45 25 50 60 30 20 40 70 After make heap(a, a+10):

80 70 60 40 50 45 30 20 25 10 After X = *a and pop heap(a, a+10):

70 50 60 40 10 45 30 20 25 After a[9] = x and push heap(a, a+10):

80 70 60 40 50 45 30 20 25 10 After sort heap(a, a+10):

10 20 25 30 40 45 50 60 70 80

После вызова make heap первый элемент наибольший, но последовательность не является отсортированной в нисходящем порядке; например, 40 предшествует 50. Однако она является пирамидой, поэтому, после копирования первого элемента (80) в переменную х, мы можем использовать алгоритм popjieap, чтобы получить пирамиду из девяти элементов. Это значение (80) снова добавляется в пирамиду: сначала мы помещаем его в конец последовательности, а затем вызываем алгоритм pushjieap для восстановления условия пирамидальности. Кроме всего, пирамида сортируется с помощью специального алгоритма sortjeap, который использует свойства пирамиды и поэтому работает быстрее, чем алгоритм общего назначения sort.

7.3.10. Минимум и максимум

const Т& min

(const Т& а, const Т& Ь); const Т& min

(const Т& а, const Т& Ь, Compare comp); const Т& max

(const Т& a, const T& b); const T& max

(const T& a, const T& b. Compare comp); Forwardlterator min element

(Forwardlterator first, Forwardlterator last); Forwardlterator min element

(Forwardlterator first, Forwardlterator last. Compare comp); Forwardlterator /nax ele/nent

(Forwardlterator first, Forwardlterator last); Forwardlterator max element

(Forwardlterator first, Forwardlterator last. Compare comp);

int main()

{ int X = 123, у = 75, minimum, MaxLastDigit; minimum = min(x, y);

MaxLastDigit = max(x, y, CompareLastDigit); cout << minimum << MaxLastDigit endl; return 0; Вывод: 75 7 5

В этой программе вызов min возвращает 75, меньшее из чисел 123 и 75. Вызов max также возвращает 75, потому что последняя цифра (5) этого числа больше, чем последняя цифра числа 123.

Чтобы найти позицию наименьшего элемента в последовательности, мы можем использовать алгоритм min element. В следующей программе этот алгоритм используется для массива и для списка:

min elt.cpp: Наименьший элемент последовательности, iinclude <iostream> iinclude <list> iinclude <algorithm> using namespace std;

int mainO

{ int a[5] = {10, 30, 5, 40, 20), *p; list<int> L;

L.insert(L.begin 0, a, a+5); list<int>::iterator i; p = min element(a, a+5);

Если мы хотим найти минимум или максимум двух объектов, для которых определен оператор <, то можем использовать алгоритмы min и max, реализовать которые можно, например, следующим хорошо известным способом:

#define min(x, у) ((х) < (у) ? (х) : (у)) ♦define max(x, у) ((х) < (у) ? (у) : (х))

Существуют также версии алгоритмов min и max с третьим аргументом, задающим операцию сравнения. Следующая программа использует min с двумя и max с тремя элементами:

minmax.cpp: Алгоритмы min и max. ♦include <iostream> iinclude <algorithm> iinclude <functional> using namespace std;

bool CompareLastDigit(int x, int y) { return X % 10 < у % 10;

i = min element (L. begin!) , L.endO); cout *p *i << endl; Вывод: 5 5 return 0;

Существует также версия алгоритма min element, которая имеет третий аргумент для передачи ему операции сравнения аналогично тому, как это сделано для алгоритмов min и max. Если мы хотим найти позицию максимального элемента в последовательности, можно использовать алгоритм maxjelement, который имеет те же два варианта, что и min element.

7.3.11. Лексикографическое сравнение

bool lexicographical compare

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2); bool lexicographical compare

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2. Compare comp);

Мы можем проводить лексикографическое сравнение последовательностей аналогично тому, как мы сравниваем строки текста: если первые элементы различны, они определяют результат сравнения, в противном случае мы сравниваем вторые элементы и т. д. Существуют два алгоритма lexicographicaljcompare: один с четырьмя параметрами использует для сравнения элементов операцию <, другой же принимает операцию сравнения в качестве дополнительного аргумента. Пример работы этих алгоритмов приведен в следующей программе:

lexcomp.cpp: Лексикографическое сравнение, ♦include <iostream> ♦include <algorithm> ♦include <functional> using namespace std;

int mainO

{ int a[4] = {1, 3, 8, 2}, b[4] = {1, 3, 9, 1};

cout a: ;

copy(a, a+4, ostream iterator<int>(cout, ));

cout \nb: ;

copy(b, b+4, ostream iterator<int>(cout, ));

cout endl;