будет содержать минимум повторений. Давайте заменим в только что рассмотренной программе инициализацию переменной а, в результате чего вторая строчка функции main будет выглядеть вот так:

{ int а[4] = {1, 1, 7, 8), Ь[3] = {2, 5, 8),

После такого изменения мы получим следующий вывод:

а: 117 8

Ь: 2 5 8

sum: 112 5 7 8

prod: 8

dif: 117

symdif: 112 5 7

a does not include b.

sum includes b.

7.3.9. Операции над пирамидами

void push heap

(RandomAccessIterator first,

RandomAccessIterator last); void push heap

(RandomAccessIterator first,

RandomAccessIterator last. Compare comp); void pop heap

(RandomAccessIterator first,

RandomAccessIterator last); void pop heap

(RandomAccessIterator first,

RandomAccessIterator last. Compare comp); void make heap

(RandomAccessIterator first,

RandomAccessIterator last); void niake heap

(RandomAccessIterator first,

RandomAccessIterator last. Compare comp); void sort heap

(RandomAccessIterator first,

RandomAccessIterator last); void sort heap

(RandomAccessIterator first,

RandomAccessIterator last. Compare comp);

Пирамида (heap) - это особый способ организации элементов в диапазоне [start, end), где start и end - итераторы произвольного доступа. Рассмотрим следующий пример пирамиды:

i-> 9123456789

a[i] -> 80 70 60 40 50 45 30 25 20 10

В этом примере, как и в любой пирамиде из десяти элементов, у нас:

fl[0] не меньше, чем а[1] и а[2], а[1] не меньше, чем а[3] и а[А], а[2] не меньше, чем а[5] и fl[6], а[3] не меньше, чем а[7] и fl[8], fl[4] не меньше, чем fl[9].

Вообще говорят, что контейнер а с элементами fl[0], a[i],а[п - 1] удовлетворяет условию пирамидалъностпи, если

a[i]>a[2*i + 1] а[г\ >a[2*i + 2]

для всех элементов, принадлежащих контейнеру. Отсюда следует, что первый элемент (fl[0]) пирамиды является наибольшим. Пирамиды удобно использовать для реализации очередей с приоритетами, рассмотренных в разделе 5.3, поскольку существуют операции эффективного извлечения первого элемента и добавления нового элемента с сохранением условия пирамидальности. Извлечение первого элемента пирамиды в STL реализовано следующим образом: сначала мы копируем первый элемент как обычно, а затем вызываем алгоритм pop heap. Например, для массива а мы можем написать

X = *а; pop heap(a, а+10);

а для вектора или двусторонней очереди v:

X = *v.begin(); pop heap (v.begin() , v.endO);

Функция popjieap логически удаляет первый элемент контейнера, а затем восстанавливает условие пирамидальности.

Добавляем новый элемент в пирамиду мы также с помощью двух операций: сперва помещаем новый элемент в конце пирамиды, а затем вызываем алгоритм pushjieap. Например:

а[9] = х; push heap(a, а+10); или

v.push back(х); push heap(v.begin(), v.endO);

Алгоритм push heap восстанавливает условие пирамидальности, если только последний элемент последовательности нарушает это условие.

i<10; i++) cout << i;

int mainO { cout <<

for (int i=0;

cout endl;

int a[10] = (20, 50, 40, 60, 80, 10, 30, 70, 25, 45}; show( Initial contents of a: , a, a+10); random shuffle(a, a+10);

showCAfter random shuffle(a, a+10): , a, a+10); make heap(a, a+10);

show( After make heap(a, a+10): , a, a+10);

int X = *a; pop heap(a, a+10);

show( After X = *a and pop heap(a, a+10): , a, a+9); a[9] = x;

push heap(a, a+10);

show( After a[9] = x and push heap(a, a+10): ,

a, a+10); sort heap(a, a+10);

show( After sort heap(a, a+10): , a, a+10); return 0;

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

Существует более мощная (но требующая больше времени для выполнения) функция make heap, которая превращает последовательный контейнер с произвольным доступом в пирамиду. И наконец, мы можем использовать алгоритм sort heap для превращения пирамиды в отсортированную последовательность. Обратите внимание, что этот алгоритм помещает элементы в восходящем порядке, так что они перестают удовлетворять условию пирамидальности. Упомянутые выше алгоритмы работы с пирамидами используются в следующей программе:

heapdemo.срр: Демонстрация операций с пирамидами, ttinclude <iostream> iinclude <algorithm> using namespace std;

void show( const char *s, const int *begin,

const int *end) { cout s << endl <<

copy(begin, end, ostream iterator<int>(cout, ));

cout << endl;