Двоичная куча
Двоичная куча (она же Пирамида, она же Cортирующее дерево) - это структура данных, двоичное дерево, значение в каждом узле которого не меньше значений его потомков. Заполнение элементами последнего слоя происходит слева направо, без пропусков. При выполнении этих условий, элементы кучи удобно хранить в одномерном массиве. Корень дерева будет иметь индекс 0. У любого i-го элемента его дочерние узлы будут иметь индексы 2*i+1 и 2*i+2.
Ниже реализация класса бинарной кучи на Delphi, все остальные комментарии - в исходном тексте.
unit uHeap;
interface
uses
Generics.Collections
,Generics.Defaults
;
type
/// <summary>
/// Бинарная куча
/// </summary>
/// <typeparam name="T">
/// Тип элементов кучи
/// </typeparam>
TBinaryHeap<T> = class
private
FHeap : TList<T>; // Список для хранения элементов
FComparer : IComparer<T>; // Компаратор элементов
function GetSize : integer;
protected
/// <summary>
/// Упорядочивание кучи
/// </summary>
/// <param name="i">
/// Порядковый номер элемента, с которого начинается
/// упорядочивание
/// </param>
procedure Heapify(i: integer);
/// <summary>
/// Получение элемента из кучи
/// </summary>
/// <param name="Index">
/// Порядковый номер элемента
/// </param>
function GetItem(Index: integer): T;
public
/// <summary>
/// Конструктор бинарной кучи
/// </summary>
/// <param name="AComparer">
/// Компаратор, поддерживающий интерфейс IComparer
/// для элементов кучи
/// </param>
constructor Create(const AComparer: IComparer<T>); overload;
/// <summary>
/// Конструктор бинарной кучи
/// </summary>
/// <param name="Values">
/// Массив значений, которыми будет инициализирована
/// куча
/// </param>
/// <param name="AComparer">
/// Компаратор, поддерживающий интерфейс IComparer
/// для элементов кучи
/// </param>
/// <remarks>
/// Эквивалентно созданию кучи и добавлению значений
/// через Add(Values)
/// </remarks>
constructor Create(Values: Array of T; const AComparer: IComparer<T>); overload;
/// <summary>
/// Добавление элемента
/// </summary>
/// <param name="Value">
/// Новый элемент
/// </param>
/// <remarks>
/// После добавления происходит упорядочивание кучи.
/// </remarks>
procedure Add(Value: T); overload;
/// <summary>
/// Добавление массива элементов.
/// </summary>
/// <param name="Values">
/// Массив новых элементов
/// </param>
/// <remarks>
/// После всех добавлений происходит упорядочивание
/// кучи. Поскольку оно происходит один раз, это
/// быстрее, чем добавление по одному элементу через
/// Add(value)
/// </remarks>
procedure Add(Values: Array of T); overload;
/// <summary>
/// Извлечение максимального элемента.
/// </summary>
/// <remarks>
/// Извлечённый элемент извлекается их кучи, после
/// чего куча перестраивается.
/// </remarks>
function ExtractMax: T;
/// <summary>
/// Текущий размер кучи.
/// </summary>
property Size : integer read GetSize;
/// <summary>
/// Массив элементов кучи
/// </summary>
/// <param name="Index">
/// Порядковый номер элемента
/// </param>
/// <remarks>
/// Свойство доступно только для чтения.
/// </remarks>
property Items[Index: integer]: T read GetItem;
/// <summary>
/// Деструктор кучи.
/// </summary>
destructor Destroy; override;
end;
implementation
{ TBinaryHeap<T> }
constructor TBinaryHeap<T>.Create(const AComparer: IComparer<T>);
begin
inherited Create;
FHeap := TList<T>.Create;
FComparer := AComparer;
end;
constructor TBinaryHeap<T>.Create(Values: array of T;
const AComparer: IComparer<T>);
begin
Create(AComparer);
Add(Values);
end;
procedure TBinaryHeap<T>.Add(Value: T);
var
i : integer;
parent : integer;
begin
// Добавим элемент в конец
FHeap.Add(Value);
// Новый элемент всплывает
i := Size - 1;
parent := (i - 1) div 2;
while (i > 0) and (FComparer.Compare(FHeap.Items[parent], FHeap.Items[i]) < 0) do
begin
FHeap.Exchange(i, parent);
i := parent;
parent := (i - 1) div 2;
end;
// Куча перестроена
end;
procedure TBinaryHeap<T>.Add(Values: array of T);
var
i: integer;
begin
// Добавим масив элементов
FHeap.AddRange(Values);
// и перестроим кучу
for i := Size div 2 downto 0 do
Heapify(i);
end;
function TBinaryHeap<T>.GetItem(Index: integer): T;
begin
result := FHeap.Items[Index];
end;
function TBinaryHeap<T>.GetSize: integer;
begin
result := FHeap.Count;
end;
procedure TBinaryHeap<T>.Heapify(i: integer);
var
left, right, largerst : integer;
begin
while True do
begin
// Определяем индексы дочерних элементов
left := 2 * i + 1;
right := 2 * i + 2;
largerst := i;
// Ищем дочерний, который больше текущего
if (left < Size) and (FComparer.Compare(FHeap.Items[left], FHeap.Items[largerst]) > 0)
then largerst := left;
if (right < Size) and (FComparer.Compare(FHeap.Items[right], FHeap.Items[largerst]) > 0)
then largerst := right;
// Если большего не нашлось, упорядочивание закончилось. Уходим.
if i = largerst then Exit;
// Обменяем местами узлы
FHeap.Exchange(i, largerst);
// и продолжим упорядочивать заменённый дочерний
i := largerst;
end;
end;
function TBinaryHeap<T>.ExtractMax: T;
begin
// Извлекаем вершину дерева, это максимальный элемент
result := FHeap.Items[0];
// Переносим последний элемент на место вершины
FHeap.Items[0] := FHeap.Items[FHeap.Count - 1];
FHeap.Delete(FHeap.Count - 1);
// и перестраиваем кучу
Heapify(0);
end;
destructor TBinaryHeap<T>.Destroy;
begin
FHeap.Free;
inherited;
end;
end.
Пример использования этого класса можно посмотреть в Пирамидальной сортировке.
Метки: