Binary Heap (двоичная куча)

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

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

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

  • Значение в любой вершине не меньше чем значение в потомках
  • Расстояние до корня отличается не более чем на один уровень
  • Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

  • Достать максимальный элемент из кучи, не удаляя его
  • Добавить элемент в кучу
  • Создать кучу
  • Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
  • Узнать размер кучи
  • Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: [latex]O(\log(n))[/latex]

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: [latex]O(1)[/latex]

3. Удаление максимального элемента

Меняются местами первая и последняя вершины, после чего последняя вершина запоминается и удаляется, а новая первая вершина проталкивается в кучу, согласно её свойствам.

Сложность: [latex]O(\log(n))[/latex]

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: [latex]O(n\log(n))[/latex]

О реализации

Реализуется структура данных с абстрактным типом данных.  Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером [latex]i[/latex] её левый сын хранится в [latex]2*i+1[/latex] вершине, а правый — в [latex]2*i+2[/latex] вершине.

Класс содержит следующие методы:

  • Heap() — конструктор
  • shiftUp() — восходящее восстановление свойства кучи
  • shiftDown() — нисходящее восстановление свойства кучи
  • insert() — добавление элемента в кучу
  • delete() — удаление первой вершины
  • size() — размер кучи
  • isEmpty() — проверка на пустоту
  • toString() — преобразование в строку
  • max() — максимальный элемент
  • print() — вывод кучи на экран

Код