Куча или структура данных — это специальная форма данных по типу дерева, удовлетворяющая условиям кучи. А именно, если В есть узел-потомок узла А, то ключ(A) ≥ ключ(B).
Структура данных куча
Предположим, что имеется структура данных, поддерживающая такой операционный набор:
- Добавление элемента в эту структуру.
- Извлечение из данной структуры самого большого или самого маленького компонента. Компонент после извлечения должен быть удалён из структуры.
При всём при этом в структуре данных возможно хранение одинаковых компонентов. Если данная структура реализована на основе списка, то возможно прибавление компонентов в конец списка за О(1). Однако нахождение самого большого компонента определяется сложностью О(n) и если под n понимается количество компонентов в списке, то надо обойти все компоненты списка и взять самый большой. В случае сохранения компонентов в списке в упорядоченном виде по их возрастанию, то в этом случае процесс извлечения максимального элемента займёт О(1). А, чтобы добавить компонент в список, надо затратить О(n), поскольку необходимо выполнить сдвиг компонентов уже имеющихся в списке. Специальная организация данных «Куча» (английское heap) даёт возможность осуществлять такие процедуры с меньшими затратами. В структуре данных типа куча компоненты представлены в формате двоичного дерева, что означает наличие у компонентов двух потомков, слева и справа. Вершиной кучи является один компонент, у которого есть два потомка на следующем уровне. У них также имеется по два потомка у каждого на третьем уровне. То есть суммарно четыре компонента на третьем уровне и так далее. Заполнение уровней выполняется по возрастанию номера уровня, а непосредственно заполнение уровня идёт слева направо. Компоненты последнего уровня не имеют потомков и есть вероятность их отсутствия и у отдельных компонентов на предпоследнем уровне. Кроме того, в составе кучи возможно наличие одного компонента, имеющего только одного (левого) потомка. Все составляющие элементы кучи обладают отличительной особенностью, любой элемент кучи больше или равен относительно своих потомков. Отсюда следует, что вершиной кучи является самый большой компонент. Ниже приводится пример стандартной кучи, состоящей из девяти компонентов.
Рисунок 1. Пример стандартной кучи. Автор24 — интернет-биржа студенческих работ
Сохранять компоненты в списке оптимально, помещая в начало корневой компонент. Чтобы упростить нумерацию, можно пропустить нулевой номер, то есть поместить вершину кучи в компонент, имеющий индекс номер один. Оставшиеся компоненты кучи будут храниться последовательно и иметь индексы в порядке возрастания, то есть два, три, четыре и так далее. Для приведённого выше примера, список имеет следующий вид:
H[1] == 100
H[2] == 19
H[3] == 36
H[4] == 17
H[5] == 3
H[6] == 25
H[7] == 1
H[8] == 2
H[9] == 7
Следует отметить, что компонент Н(i) имеет левого потомка с индексом Н(2i), а правого потомка с индексом H[2i+1]. В качестве родителя компонента H[i] выступает компонент H[i/2].
Прибавление компонента в кучу
Чтобы добавить компонент в кучу, необходимо выполнить следующие действия. Изначально компонент помещается последним в куче. Это делается посредством способа append списка. Однако это может нарушить основное качество кучи, а именно, все компоненты превышают своих потомков. Это может случиться, если есть компонент, являющийся родителем того, который добавили. В таком случае необходимо поменять их местами. Эта процедура должна повторяться пока присутствует нарушение основного условия, то есть добавляемый компонент имеет родителя, который не является корневым и меньше, чем добавляемый. Таким образом, осуществляется «подъём» прибавляемого компонента на верх кучи, пока он не получит соответствующее его статусу место. Ниже приведена программа выполнения данного алгоритма с незначительной его оптимизацией:
Рисунок 2. Прибавление компонента в кучу. Автор24 — интернет-биржа студенческих работ
Фунция add получает два параметра, список, где сохранена куча, и элемент, который надо добавить (elem). Первоначально к концу кучи прибавляется новый компонент, а переменная i получает индекс прибавляемого компонента. Далее все предки прибавляемого компонента могут быть передвинуты вниз, в случае, если добавляемый компонент больше каждого из них. Эта процедура осуществляется циклом while. По завершению цикла вместо компонента I пишется содержимое elem.
Удаление компонента из состава кучи
Из состава кучи возможно удаление самого большого компонента, то есть находящегося на вершине кучи. Его место может занять какой-либо компонент кучи. Установим последний компонент кучи путём удаления его из конца. В этом случае в вершине кучи возможно нарушение её главного свойства, и это означает необходимость смещения верхнего компонента вниз, поменяв его местами с каким-либо из его потомков. Необходимо выбирать из двух потомков самый большой, и если он превышает расположенного в вершине кучи, то следует поменять их местами. Это означает, что компонент, взятый снизу кучи, опустится ниже на один уровень. Затем происходит дальнейшее опускание этого компонента вниз до того момента, пока он не станет больше обоих его потомков. Или у него совсем не останется потомков.
Рисунок 3. Удаление компонента из состава кучи. Автор24 — интернет-биржа студенческих работ
В данном примере величина компонента вершины кучи хранится в операторе retval, далее последний компонент убирается из кучи и переносится на её вершину. Особняком стоит вариант, когда в куче всего один компонент, то есть когда он удаляется, куча оказывается пуста. Затем в главном цикле элемент опускают ниже.
