20  50  40  60   80   10  30  70  25  45 After random_shuffle(a,   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 для восстановления условия пирамидальности. Кроме всего, пирамида сорти­руется с помощью специального алгоритма sortjieap, который использует свойства пирамиды и поэтому работает быстрее, чем алгоритм общего на­значения sort.

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

const T& min

(const T& a, const T& Ь); const T& min

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

(const T& 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 max_element

(Forwardlterator first, Forwardlterator last); Forwardlterator max_element

(Forwardlterator first, Forwardlterator last, Compare comp);

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

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

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

// miranax.срр:   Алгоритмы min и max. #include  <iostream> #include <algorithm> iinclude  <functional> using namespace  std;


<< назад вперед >>