1. Введение
В этом руководстве мы увидим, как работает сортировка кучей, и реализуем ее на Java.
Сортировка кучей основана на структуре данных кучи. Чтобы правильно понять сортировку кучи, мы сначала рассмотрим кучи и то, как они реализованы.
2. Структура данных кучи
Куча — это специализированная древовидная структура данных . Поэтому он состоит из узлов. Мы присваиваем элементы узлам: каждый узел содержит ровно один элемент.
Кроме того, узлы могут иметь потомков. Если узел не имеет потомков, мы называем его листом.
Отличительной чертой Heap являются две вещи:
- значение каждого узла должно быть меньше или равно всем значениям, хранящимся в его дочерних элементах .
- это полное дерево , что означает, что оно имеет наименьшую возможную высоту
Из-за 1-го правила наименьший элемент всегда будет в корне дерева .
То, как мы применяем эти правила, зависит от реализации.
Кучи обычно используются для реализации приоритетных очередей, потому что куча — это очень эффективная реализация извлечения наименьшего (или наибольшего) элемента.
2.1. Варианты кучи
У кучи много вариантов, все они отличаются некоторыми деталями реализации.
Например, то, что мы описали выше, — это Min-Heap, потому что родитель всегда меньше, чем все его дочерние элементы . В качестве альтернативы мы могли бы определить Max-Heap, и в этом случае родитель всегда больше, чем его дочерние элементы. Следовательно, наибольший элемент будет в корневом узле.
Мы можем выбирать из многих реализаций дерева. Наиболее простым является бинарное дерево. В двоичном дереве каждый узел может иметь не более двух дочерних элементов. Мы называем их левым потомком и правым потомком .
Самый простой способ применить второе правило — использовать полное двоичное дерево. Полное двоичное дерево следует нескольким простым правилам:
- если узел имеет только одного дочернего элемента, это должен быть его левый дочерний элемент
- только самый правый узел на самом глубоком уровне может иметь ровно одного потомка
- листья могут быть только на самом глубоком уровне
Давайте рассмотрим эти правила на нескольких примерах:
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. Вставка элементов
Мы должны реализовать все операции таким образом, чтобы сохранить инварианты кучи. Таким образом, мы можем построить кучу с повторяющимися вставками , поэтому мы сосредоточимся на одной операции вставки.
Мы можем вставить элемент со следующими шагами:
- создайте новый лист, который является самым правым доступным слотом на самом глубоком уровне, и сохраните элемент в этом узле
- если элемент меньше своего родителя, мы меняем их местами
- продолжайте с шага 2, пока элемент не станет меньше своего родителя или не станет новым корнем
Обратите внимание, что шаг 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;
}
}
Приведенный выше код только добавляет новый элемент в конец дерева. Следовательно, нам нужно пройти новый элемент вверх, если это необходимо. Мы можем сделать это с помощью следующего кода:
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);
}
// ...
}
Обратите внимание, что поскольку нам нужно сравнивать элементы, для них необходимо реализовать java.util.Comparable .
4. Сортировка кучей
Поскольку корень кучи всегда содержит наименьший элемент, идея сортировки кучи довольно проста: удалять корневой узел до тех пор, пока куча не станет пустой .
Единственное, что нам нужно, — это операция удаления, которая сохраняет кучу в согласованном состоянии. Мы должны убедиться, что не нарушаем структуру двоичного дерева или свойства кучи.
Чтобы сохранить структуру, мы не можем удалить ни один элемент, кроме самого правого листа. Итак, идея состоит в том, чтобы удалить элемент из корневого узла и сохранить крайний правый лист в корневом узле.
Но эта операция наверняка нарушит свойство кучи. Поэтому , если новый корень больше, чем любой из его дочерних узлов, мы меняем его местами с его наименьшим дочерним узлом . Поскольку наименьший дочерний узел меньше всех других дочерних узлов, он не нарушает свойство кучи.
Мы продолжаем менять местами до тех пор, пока элемент не станет листом или не станет меньше, чем все его дочерние элементы.
Удалим корень из этого дерева:
1
/ \
/ \
3 2
/ \ / \
5 7 6 4
Сначала помещаем последний лист в корень:
4
/ \
/ \
3 2
/ \ /
5 7 6
Затем, поскольку он больше, чем оба его дочерних элемента, мы меняем его местами с его наименьшим дочерним элементом, равным 2:
2
/ \
/ \
3 4
/ \ /
5 7 6
4 меньше 6, поэтому мы останавливаемся.
5. Реализация сортировки кучей в 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 .