«1. Введение
В этом руководстве мы увидим, как работает сортировка кучей, и реализуем ее на Java.
Сортировка кучей основана на структуре данных кучи. Чтобы правильно понять сортировку кучи, мы сначала рассмотрим кучи и то, как они реализованы.
2. Структура данных кучи
Куча — это специализированная древовидная структура данных. Поэтому он состоит из узлов. Мы присваиваем элементы узлам: каждый узел содержит ровно один элемент.
Также у узлов могут быть дочерние элементы. Если узел не имеет потомков, мы называем его листом.
Что делает Heap особенным, так это две вещи:
- every node’s value must be less or equal to all values stored in its children
- it’s a complete tree, which means it has the least possible height
Из-за 1-го правила наименьший элемент всегда будет в корне дерева.
То, как мы применяем эти правила, зависит от реализации.
Кучи обычно используются для реализации приоритетных очередей, потому что куча — это очень эффективная реализация извлечения наименьшего (или наибольшего) элемента.
2.1. Варианты кучи
У кучи есть много вариантов, все они отличаются некоторыми деталями реализации.
Например, то, что мы описали выше, является Min-Heap, потому что родитель всегда меньше, чем все его дочерние элементы. В качестве альтернативы мы могли бы определить Max-Heap, и в этом случае родитель всегда больше, чем его дочерние элементы. Следовательно, наибольший элемент будет в корневом узле.
Мы можем выбирать из многих реализаций дерева. Наиболее простым является бинарное дерево. В двоичном дереве каждый узел может иметь не более двух дочерних элементов. Мы называем их левым дочерним элементом и правым дочерним элементом.
Самый простой способ применить второе правило — использовать полное двоичное дерево. Полное двоичное дерево следует некоторым простым правилам:
- if a node has only one child, that should be its left child
- only the rightmost node on the deepest level can have exactly one child
- leaves can only be on the deepest level
Давайте рассмотрим эти правила на нескольких примерах:
1 2 3 4 5 6 7 8 9 10
() () () () () () () () () ()
/ \ / \ / \ / \ / \ / / / \
() () () () () () () () () () () () () ()
/ \ / \ / \ / / \
() () () () () () () () ()
/
()Деревья 1, 2, 4, 5 и 7 следуют правилам.
Деревья 3 и 6 нарушают 1-е правило, 8 и 9 — 2-е правило, а 10 — 3-е правило.
В этом уроке мы сосредоточимся на Min-Heap с реализацией двоичного дерева.
2.2. Вставка элементов
Мы должны реализовать все операции таким образом, чтобы сохранить инварианты кучи. Таким образом, мы можем построить кучу с повторяющимися вставками, поэтому мы сосредоточимся на одной операции вставки.
Мы можем вставить элемент, выполнив следующие шаги:
- create a new leaf which is the rightmost available slot on the deepest level and store the item in that node
- if the element is less than it’s parent, we swap them
- continue with step 2, until the element is less than it’s parent or it becomes the new root
Обратите внимание, что шаг 2 не нарушит правило кучи, потому что, если мы заменим значение узла на меньшее, оно все равно будет меньше, чем его дочерние элементы.
Давайте посмотрим на пример! Мы хотим вставить 4 в эту кучу:
2
/ \
/ \
3 6
/ \
5 7Первый шаг — создать новый лист, в котором хранится 4:
2
/ \
/ \
3 6
/ \ /
5 7 4Так как 4 меньше, чем его родитель, 6, мы меняем их местами: ~~ ~
2
/ \
/ \
3 4
/ \ /
5 7 6Теперь мы проверяем, меньше ли 4 своего родителя или нет. Поскольку его родитель равен 2, мы останавливаемся. Куча все еще действительна, и мы вставили номер 4.
Давайте вставим 1:
2
/ \
/ \
3 4
/ \ / \
5 7 6 1Мы должны поменять местами 1 и 4:
2
/ \
/ \
3 1
/ \ / \
5 7 6 4Теперь мы должны поменять местами 1 и 2:
1
/ \
/ \
3 2
/ \ / \
5 7 6 4Поскольку 1 — это новый корень, мы останавливаемся.
3. Реализация кучи в Java
Поскольку мы используем полное двоичное дерево, мы можем реализовать его с помощью массива: элемент массива будет узлом дерева. Мы помечаем каждый узел индексами массива слева направо, сверху вниз следующим образом:
0
/ \
/ \
1 2
/ \ /
3 4 5Единственное, что нам нужно, это отслеживать, сколько элементов мы храним в дереве. Таким образом, индекс следующего элемента, который мы хотим вставить, будет размером массива.
Используя эту индексацию, мы можем вычислить индекс родительского и дочернего узлов:
-
родитель: (индекс – 1) / 2 левый дочерний элемент: 2 * индекс + 1 правый дочерний элемент: 2 * индекс + 2 ~ ~~ Так как мы не хотим возиться с перераспределением массива, мы еще больше упростим реализацию и воспользуемся ArrayList.
Базовая реализация двоичного дерева выглядит так:
Приведенный выше код только добавляет новый элемент в конец дерева. Следовательно, нам нужно пройти новый элемент вверх, если это необходимо. Мы можем сделать это с помощью следующего кода:
class BinaryTree<E> {
List<E> elements = new ArrayList<>();
void add(E e) {
elements.add(e);
}
boolean isEmpty() {
return elements.isEmpty();
}
E elementAt(int index) {
return elements.get(index);
}
int parentIndex(int index) {
return (index - 1) / 2;
}
int leftChildIndex(int index) {
return 2 * index + 1;
}
int rightChildIndex(int index) {
return 2 * index + 2;
}
}Обратите внимание, что поскольку нам нужно сравнивать элементы, они должны реализовывать java.util.Comparable.
class Heap<E extends Comparable<E>> {
// ...
void add(E e) {
elements.add(e);
int elementIndex = elements.size() - 1;
while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) {
int parentIndex = parentIndex(elementIndex);
swap(elementIndex, parentIndex);
elementIndex = parentIndex;
}
}
boolean isRoot(int index) {
return index == 0;
}
boolean isCorrectChild(int index) {
return isCorrect(parentIndex(index), index);
}
boolean isCorrect(int parentIndex, int childIndex) {
if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) {
return true;
}
return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0;
}
boolean isValidIndex(int index) {
return index < elements.size();
}
void swap(int index1, int index2) {
E element1 = elementAt(index1);
E element2 = elementAt(index2);
elements.set(index1, element2);
elements.set(index2, element1);
}
// ...
}4. Сортировка кучей
Поскольку корень кучи всегда содержит наименьший элемент, идея сортировки кучей довольно проста: удалять корневой узел до тех пор, пока куча не станет пустой.
«Единственное, что нам нужно, — это операция удаления, которая сохраняет кучу в согласованном состоянии. Мы должны убедиться, что не нарушаем структуру двоичного дерева или свойства кучи.
Чтобы сохранить структуру, мы не можем удалить ни один элемент, кроме самого правого листа. Итак, идея состоит в том, чтобы удалить элемент из корневого узла и сохранить крайний правый лист в корневом узле.
Но эта операция наверняка нарушит свойство кучи. Поэтому, если новый корень больше, чем любой из его дочерних узлов, мы меняем его местами с его наименьшим дочерним узлом. Поскольку наименьший дочерний узел меньше всех других дочерних узлов, он не нарушает свойство кучи.
Мы продолжаем менять местами до тех пор, пока элемент не станет листом или не станет меньше, чем все его дочерние элементы.
Давайте удалим корень из этого дерева:
Сначала мы поместим последний лист в корень:
1
/ \
/ \
3 2
/ \ / \
5 7 6 4Затем, поскольку он больше, чем оба его дочерних элемента, мы поменяем его местами с его наименьший дочерний элемент, равный 2:
4
/ \
/ \
3 2
/ \ /
5 7 64 меньше 6, поэтому мы останавливаемся.
2
/ \
/ \
3 4
/ \ /
5 7 65. Реализация сортировки кучи в Java
Со всем, что у нас есть, удаление корня (выталкивание) выглядит следующим образом:
Как мы уже говорили ранее, сортировка — это просто создание кучи и удаление корня повторно:
class Heap<E extends Comparable<E>> {
// ...
E pop() {
if (isEmpty()) {
throw new IllegalStateException("You cannot pop from an empty heap");
}
E result = elementAt(0);
int lasElementIndex = elements.size() - 1;
swap(0, lasElementIndex);
elements.remove(lasElementIndex);
int elementIndex = 0;
while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) {
int smallerChildIndex = smallerChildIndex(elementIndex);
swap(elementIndex, smallerChildIndex);
elementIndex = smallerChildIndex;
}
return result;
}
boolean isLeaf(int index) {
return !isValidIndex(leftChildIndex(index));
}
boolean isCorrectParent(int index) {
return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index));
}
int smallerChildIndex(int index) {
int leftChildIndex = leftChildIndex(index);
int rightChildIndex = rightChildIndex(index);
if (!isValidIndex(rightChildIndex)) {
return leftChildIndex;
}
if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) {
return leftChildIndex;
}
return rightChildIndex;
}
// ...
}Мы можем проверить его работу с помощью следующего теста:
class Heap<E extends Comparable<E>> {
// ...
static <E extends Comparable<E>> List<E> sort(Iterable<E> elements) {
Heap<E> heap = of(elements);
List<E> result = new ArrayList<>();
while (!heap.isEmpty()) {
result.add(heap.pop());
}
return result;
}
static <E extends Comparable<E>> Heap<E> of(Iterable<E> elements) {
Heap<E> result = new Heap<>();
for (E element : elements) {
result.add(element);
}
return result;
}
// ...
}Обратите внимание, что мы могли бы предоставить реализацию, которая сортирует на месте, что означает, что мы предоставляем результат в том же массиве, который мы получил элементы. Кроме того, таким образом нам не нужно промежуточное выделение памяти. Однако эту реализацию будет немного сложнее понять.
@Test
void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() {
// given
List<Integer> elements = Arrays.asList(3, 5, 1, 4, 2);
// when
List<Integer> sortedElements = Heap.sort(elements);
// then
assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5));
}6. Временная сложность
Сортировка кучей состоит из двух ключевых шагов: вставки элемента и удаления корневого узла. Оба шага имеют сложность O(log n).
Поскольку мы повторяем оба шага n раз, общая сложность сортировки составляет O(n log n).
Обратите внимание, что мы не упомянули стоимость перераспределения массива, но так как это O(n), это не влияет на общую сложность. Кроме того, как мы упоминали ранее, можно реализовать сортировку на месте, что означает, что перераспределение массива не требуется.
Также стоит отметить, что 50% элементов — это листья, а 75% элементов находятся на двух нижних уровнях. Поэтому большинство операций вставки не требуют более двух шагов.
Обратите внимание, что на реальных данных быстрая сортировка обычно более эффективна, чем сортировка кучей. Положительным моментом является то, что Heap Sort всегда имеет временную сложность O(n log n) в наихудшем случае.
7. Заключение
В этом руководстве мы рассмотрели реализацию двоичной кучи и сортировки кучи.
Несмотря на то, что временная сложность составляет O(n log n), в большинстве случаев это не лучший алгоритм для реальных данных.
Как обычно, примеры доступны на GitHub.
«