У нас на очереди популярная и столь же быстрая как предыдущая пирамидальная сортировка. Но для понимания её принципа действия нам потребуется понять, что из себя представляет такая структура данных как «Куча» (англ. Heap). Именно ей мы и посветим данную статью. Куча представляет собой «пирамиду» из чисел. В программировании такая структура данных называется бинарное дерево. Бинарное дерево – это структура данных дерева, в которой у каждого родительского узла может быть не больше двух потомков. Т...

Классический способ реализации очереди с приоритетом - использовать структуру данных под названием двоичная куча. Она позволит нам извлекать из неё элементы за O(log(n). Кучей называется дерево, в котором любой элемент не меньше своего родителя. три основные операции, производимые с кучей: Так как мы говорим про двоичную кучу, то к ней накладываются дополнительные ограничения: Двоичная куча (структура данных) — это полное двоичное дерево, удовлетворяющее свойству кучи: если узел A — это родитель узла B, то ключ узла A ≥ ключ узла B...