Двоичная куча
Двоичная куча (она же Пирамида, она же 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.
Пример использования этого класса можно посмотреть в Пирамидальной сортировке.
Метки:
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии