Двоичная куча

Двоичная куча (она же Пирамида, она же 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.

Пример использования этого класса можно посмотреть в Пирамидальной сортировке.