Задача №3493. Пирамида (минимум)
Задача отличается от задачи «Пирамида (максимум)» исключительно тем, что надо извлекать не максимум, а минимум.
Напишите программу, которая будет обрабатывать последовательность запросов таких видов:
CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.
ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.
EXTRACT — вынуть из пирамиды минимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное минимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).
Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату.
Суммарное количество всех запросов не превышает 200000.
Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).
Собственно, это тот случай, когда, не имея под руками справочных материалов, легче реализовать структуру данных самому, чем добиться от стандартной реализации, чтобы она заработала так как надо... Но это все же возможно. Пирамиду с максимумом в корне объявляют просто как
priority_queue<T> the_heap; а пирамиду с минимумом в корне — как
priority_queue<T, vector<T>, greater<T> > the_heap; При этом, второй параметр (vector<T>) задает тип контейнера, в котором будет храниться пирамида (и менять вектор на что бы ни было другое практически никогда не бывает целесообразно), а третий параметр (который, когда ничего не сказано, равен less<T>) задает, какую операцию следует использовать при проверке основного свойства пирамиды в качестве операции «меньше». Когда на место операции «меньше» подставляется операция «больше» — как раз и получается, что упорядоченность пирамиды заменяется на противоположную.
Разумеется, вместо T следует написать тип элементов, которые будем хранить в пирамиде.
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT
125 321 7 555 CANNOT