Куча

Я решил, что быстрая сортировка вам всё-таки не нужна, поэтому расскажу про структуру данных — пирамиду.

Что мы хотим?

Необходимо реализовать структуру данных, поддерживающую две операции:

1. Добавить в структуру число x
2. Узнать минимальное число в структуре и удалить его

Как это сделать?

Рассмотрим наивные способы.

Первый способ — храним всё в массиве.

Запрос типа 1: добавляем число x в конец массива.
Запрос типа 2: проходим по массиву, находим минимум, потом удаляем его.

Я надеюсь, ты знаешь, как удалять произвольный элемент из массива.

Первый запрос, очевидно, работает за константное число операций (будем говорить, что такой запрос работает "за единицу / за 1 операцию", так как константы мы убираем), второй — за N операций в худшем случае (N — длина массива).

Это очень плохо.

Второй способ — храним всё в массиве, который поддерживаем упорядоченным по убыванию

Запрос типа 1: проходим по массиву, подбираем место, куда вставить x так, чтобы массив остался упорядоченным по убыванию, вставляем.
Запрос типа 2: искомый элемент последний

Я также надеюсь, что ты знаешь, как добавлять элемент на произвольное место в массиве. Ещё я уверен, что ты знаешь бинпоиск, ведь я его рассказывал в Летней школе.

Даже если в запросе типа 1 мы будем делать бинпоиск, на вставку в худшем случае всё ещё требуется порядка N операций. Зато запрос типа 2 делается за единицу.

Это всё ещё очень плохо. Потому что наверняка на олимпиаде будут тесты, где очень много раз числа добавляют или очень много раз числа убирают. И ваша программа решит не работать (а точнее работать очень долго) на таких тестах, так быть не должно.

Как надо?

Давайте представим дерево. Красивое дерево, у которого корень будет вверху.

Из каждого узла (в том числе из корня) выходит не более двух веток.

В каждом узле (из которого выходят ветки, в том числе и в корне) будет написано число.

Число в каждом узле не больше чисел, написанных на других концах выходящих из узла веток.

Последнее свойство — дерево заполняется числами по уровням сверху вниз, а внутри каждого уровня слева направо.

То есть на рисунке ниже нарисованы неправильные деревья, так как они заполняются не по таким правилам:

Дерево, построенное по всем таким правилам, называется двоичной кучей или пирамидой.

Как же эта структура может быть связана с нашими операциями?

Научимся добавлять элемент в него

Пусть мы хотим добавить элемент 3 в дерево 0. Добавим его на первое "вакантное" место, забыв о том, что числа должны быть упорядочены, то есть вот так:

Теперь посмотрим на тройку и на её родителя: семерку. Понятно, что здесь свойство нарушилось — значит, эти элементы стоит поменять:

Продолжим менять её с родителем дальше, пока свойство нарушается. Заметим, что обмен не нарушает ни одного другого правила.

Итоговое дерево будет снова правильным.

Теперь мы умеем добавлять элемент и узнавать минимум. Но как его удалять?

Допустим, мы хотим удалить минимальный элемент в дереве 1.

Сделаем супер-фокус: поменяем его и элемент на последнем занятом месте.

Теперь про двойку можно спокойно забыть и убрать её.

Нарушились связи между семеркой и её "потомками". Поменяем её с одним из потомков. С каким? Если поменять с большим — тогда между этим элементом и меньшим потомком возникнет нарушение правил. Тогда нужно менять с меньшим.

Меняем и далее, получим итоговое дерево.

Как видим, все правила опять соблюдаются.

Как это хранить?

Кажется, что эту структуру мы хранить не сможем, однако, это не так. Сохраним её в обычном массиве. Подряд сложим все уровни сверху вниз: на рисунке в каждом элементе написан его индекс в массиве.

У элемента с индексом k индексы потомков будут равны (2k+1) и (2k+2) (если не верите, можете убедиться).

При этом, если элементов в такой структуре N, то высота дерева будет примерно равна двоичному логарифму из N. Но при любой из двух операций число обменов с предками/потомками будет не больше высоты дерева — то есть любая операция делается за log N.

Бонус

А вот и ещё одно применение кучи: если взять произвольный массив, добавить все его элементы в кучу, а потом достать их, получится отсортированный массив. Это называется пирамидальной сортировкой.

Задания

Задание 0: я написал вот такую кучу: http://ideone.com/MRaHHM. Попробуй разобраться в моём коде.

Задание 1: напиши кучу, не смотря на код из задания 0.

Задание 2: узнай, есть ли встроенная куча в C++. Если да, то научись ей пользоваться.

Задание 3: напиши пирамидальную сортировку.

Задачи: на информатиксе