Куча и очередь с приоритетом

Коротко: Куча — дерево, в котором каждый узел меньше (min-куча) или больше (max-куча), чем его потомки. Поэтому наименьший или наибольший элемент всегда наверху.

Подробнее: Очередь с приоритетом всегда первым отдаёт элемент с наивысшим приоритетом. С кучей вставка и извлечение занимают лишь O(log n). Чтение минимума стоит O(1).