Предположим, что в кучу, изображенную на рисунке,

необходимо добавить новый элемент с ключом 17. При выполнении операции добавления элемента, он должен поместится на свободное место, т.е. позицию с индексом Num + 1. Однако эта позиция может не соответствовать правильному положению элемента в куче, так как над ним может находиться элемент, имеющий меньший приоритет. Так, при добавлении элемента с ключом 17, для вершины с индексом 5 нарушается основное свойство кучи. Простейшим способом разрешения этой ситуации является обмен элементов, на которых произошло нарушение основного свойства. При этом элемент с большим приоритетом поднимается вверх, а элемент с меньшим приоритетом занимает его место. Легко видеть, что при таком обмене свойство для вершин, стоящих ниже, не нарушается. Такое преобразование приводит к новому полному бинарному дереву, которое еще не удовлетворяет основному свойству кучи (для вершины с индексом 2). Поэтому применяем аналогичный обмен для вершины с индексом 5. Результат этого преобразования изображен ниже. В результате получено полное бинарное дерево, которое удовлетворяет основному свойству кучи. Поэтому, процедура добавления элемента завершена.

Приведем программную реализацию операции добавления элемента x к бинарной куче.

procedure insert(x:integer; var H: array [0..n] of integer; var Num, code:integer);
var i:integer;
begin
if Num = n then code := 1
else
{
Num := Num + 1;
i := Num;
H[0] := x;
while (x < H[i div 2]) do
{
H[i] := H[i div 2];
i := i div 2;
}
H[i] := x;
code := 0;
}
end;

Трудоемкость операции добавления определяется количеством выполнения цикла while и не превышает количества уровней кучи, которое равно log2Num.

Рассмотрим сейчас реализацию операции удаления минимального элемента.

В силу основного свойства кучи элемент с максимальным приоритетом находится в корне полного бинарного дерева, т.е. имеет индекс 1. Поэтому, после удаления первого элемента, его место займет тот из его сыновей или последний элемент, кто имеет больший приоритет. Освободившееся место сына займет его сын или последний элемент, и так далее. После таких преобразований внутри кучи не должно остаться "свободных" мест. Ниже приводится последовательность действий после удаления минимального элемента из бинарной кучи ("претенденты" на свободное место выделены).

Удаление минимального элемента

Функция удаления минимального элемента из бинарной кучи может быть реализована следующим образом.

function delete_min(var H: array [0..n] of integer; var Num, code: integer):integer;
var i, child:integer;
last_el:integer;
stop:boolean;
begin
if Num = 0 then code := 2
else
{
delete_min := H[1]; last_el := H[Num];
Num:= Num - 1; i := 1; stop := False;
while (2 * i <= Num) and (not stop) do
{
child := 2 * i;
if child < Num then
if H[child + 1] < H[child] then
child := child + 1;
if last_el > H[child] then
{
H[i] := H[child]; i := child;
}
else stop := True;
}
H[i] := last_el; code := 0;
}
end;

Трудоемкость операции удаления определяется количеством выполнения цикла while и не превышает количества уровней кучи, которое равно log2Num.

Одним из способов создания бинарной кучи для последовательности A из n элементов может быть выполнение n раз процедуры добавления элемента. Так как сложность процедуры добавления нового элемента в бинарную кучу есть O(log2n), то сложность построения бинарной кучи стоило бы ожидать порядка O(n log2n).

Покажем, что существует алгоритм построения бинарной кучи с трудоемкостью O(n).

Первоначально для последовательности A из n элементов строим полное бинарное дерево:

for i := 1 to n do H[i] := A[i];
Num:=n;

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

for i := (n div 2) downto 1 do percolate_down(H, Num, i);

Здесь percolate_down( H, Num, i) – процедура, обеспечивающая выполнение инварианта для вершины с индексом i. Данная процедура состоит в перемещении текущего элемента вниз до тех пор, пока для него не будет обеспечен инвариант. Такая процедура может быть реализована следующим образом:

procedure percolate_down(var H: array [0..n] of integer; Num, i:integer);
var child:integer; last_el:integer; stop:boolean;
begin
last_el := H[i]; stop := False;
while (2 * i <= Num) and (not stop) do
{
child := 2 * i;
if child < Num then
if H[child + 1] < H[child] then child := child + 1;
if last_el > H[child] then
{
H[i] := H[child];
i := child;
}
else stop := True;
}
H[i] :=last_el;
end;

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

Рассмотренная структуру можно использовать для сортировки элементов. Для этого достаточно вначале добавить каждый из них в кучу, а затем поочередно удалить. Трудоемкость сортировки, реализованной таким образом, определяется трудоемкостью операций добавления и удаления минимального элемента.
На практике алгоритм сортировки с помощью кучи не является самым быстрым — как правило, быстрая сортировка работает быстрее. Однако сама куча как структура данных часто оказывается полезной.
Очередь с приоритетами может, например, использоваться в операционной системе с разделением времени. При этом хранится список заданий с приоритетами; как только выполнение очередного задания заканчивается, из очереди выбирается задание с наибольшим приоритетом (операция удаление минимального элемента). Новые задания добавляются в очередь с помощью операции добавление.
Другое применение той же структуры — управляемое событиями моделирование (event-driven simulation). В очереди находятся события, а приоритет определяется временем, когда событие должно произойти. Разумеется, события должны моделироваться в том порядке, в котором они происходят. Выбор очередного события производится с помощью операции удаления минимального элемента (порядок здесь обратный), добавление событий — с помощью операции добавление.

С помощью кучи быстро находится k-ый элемент последовательности. Для этого нужно поместить все элементы в кучу, а затем достать из кучи k элементов. Последний из них и будет искомым. Заметим, что если k - константа, то трудоемкость данного алгоритма равна O(n) + O(k log2n) = O(n).

Кучи наиболее удобны для поиска кратчайших путей в графах с положительными длинами ребер.

Hosted by uCoz