HeapSort на Java - javascopes.com

1. введение

В этом уроке мы увидим, как работает сортировка кучи, и мы реализуем ее на Java.

Сортировка кучи основана на структуре данных кучи. Чтобы правильно понять HeapSort, мы сначала углубимся в Heaps и в то, как они реализуются.

2. Структура данных Кучи

Куча-это специализированная древовидная структура данных . Поэтому он состоит из узлов. Мы назначаем элементы узлам: каждый узел содержит ровно один элемент.

Кроме того, узлы могут иметь детей. Если у узла нет дочерних элементов, мы называем его листом.

Что делает кучу особенной, так это две вещи:

значение каждого узла должно быть меньше или равно всем значениям, хранящимся в его дочерних узлах
это полное дерево , что означает, что оно имеет наименьшую возможную высоту

Из-за 1-го правила наименьший элемент всегда будет находиться в корне дерева .

То, как мы применяем эти правила, зависит от реализации.

Кучи обычно используются для реализации очередей приоритетов, поскольку куча-это очень эффективная реализация извлечения наименьшего (или наибольшего) элемента.

2.1. Варианты кучи

Куча имеет много вариантов, все они отличаются некоторыми деталями реализации.

Например, то, что мы описали выше, является Min-кучей, потому что родитель всегда меньше, чем все его потомки . В качестве альтернативы мы могли бы определить максимальную кучу, и в этом случае родитель всегда больше, чем его дети. Следовательно, наибольший элемент будет находиться в корневом узле.

Мы можем выбирать из многих реализаций дерева. Наиболее простым является двоичное дерево. В двоичном дереве каждый узел может иметь не более двух дочерних элементов. Мы называем их левым ребенком и правым ребенком .

Самый простой способ применить 2-е правило-использовать Полное двоичное дерево. Полное двоичное дерево следует некоторым простым правилам:

если у узла есть только один дочерний элемент, это должен быть его левый дочерний элемент
только самый правый узел на самом глубоком уровне может иметь ровно одного ребенка
листья могут быть только на самом глубоком уровне

Давайте рассмотрим эти правила на нескольких примерах:

  1        2      3        4        5        6         7         8        9       10
 ()       ()     ()       ()       ()       ()        ()        ()       ()       ()
         /         \     /  \     /  \     /  \      /  \      /        /        /  \
        ()         ()   ()  ()   ()  ()   ()  ()    ()  ()    ()       ()       ()  ()
                                /          \       /  \      /  \     /        /  \
                               ()          ()     ()  ()    ()  ()   ()       ()  ()
                                                                             /
                                                                            ()

Деревья 1, 2, 4, 5 и 7 следуют правилам.

Дерево 3 и 6 нарушают 1-е правило, 8 и 9-2-е правило, а 10-3-е правило.

В этом уроке мы сосредоточимся на Min-куче с реализацией двоичного дерева .

2.2. Вставка Элементов

Мы должны реализовать все операции таким образом, чтобы сохранить инварианты кучи. Таким образом, мы можем построить кучу с повторными вставками , поэтому мы сосредоточимся на одной операции вставки.

Мы можем вставить элемент, выполнив следующие действия:

создайте новый лист, который является самым правым доступным слотом на самом глубоком уровне, и сохраните элемент в этом узле
если элемент меньше, чем его родитель, мы меняем их местами
продолжайте с шага 2, пока элемент не станет меньше, чем его родитель, или он не станет новым корнем

Обратите внимание, что шаг 2 не нарушит правило кучи, потому что, если мы заменим значение узла на меньшее, оно все равно будет меньше, чем его дочерние элементы.

Давайте рассмотрим пример! Мы хотим вставить 4 в эту кучу:

Первым шагом является создание нового листа, в котором хранятся 4:

Поскольку 4 меньше, чем у родителя, 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

Поскольку мы используем Полное двоичное дерево , мы можем реализовать его с помощью массива : элемент в массиве будет узлом в дереве. Мы помечаем каждый узел индексами массива слева направо, сверху вниз следующим образом:

Единственное, что нам нужно, – это отслеживать, сколько элементов мы храним в дереве. Таким образом, индекс следующего элемента, который мы хотим вставить, будет равен размеру массива.

Используя эту индексацию, мы можем вычислить индекс родительского и дочернего узлов:

родитель: (индекс – 1)/2
левый ребенок: 2 * индекс + 1
правый ребенок: 2 * индекс + 2

Поскольку мы не хотим беспокоиться о перераспределении массивов, мы еще больше упростим реализацию и будем использовать ArrayList .

Базовая реализация двоичного дерева выглядит следующим образом:

class BinaryTree {

    List 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> {

    // ...

    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.Сопоставимо .

4. Сортировка кучи

Поскольку корень кучи всегда содержит наименьший элемент, идея HeapSort довольно проста: удалите корневой узел, пока куча не станет пустой .

Единственное, что нам нужно, – это операция удаления, которая поддерживает кучу в согласованном состоянии. Мы должны убедиться, что не нарушаем структуру Двоичного дерева или свойства кучи.

Чтобы сохранить структуру, мы не можем удалить ни один элемент, кроме самого правого листа. Таким образом, идея состоит в том, чтобы удалить элемент из корневого узла и сохранить самый правый лист в корневом узле.

Но эта операция, безусловно, нарушит свойство кучи. Поэтому если новый корень больше любого из его дочерних узлов, мы меняем его на наименьший дочерний узел . Поскольку последний дочерний узел меньше, чем все остальные дочерние узлы, он не нарушает свойство кучи.

Мы продолжаем меняться местами до тех пор, пока элемент не станет листом или не станет меньше, чем все его дочерние элементы.

Давайте удалим корень из этого дерева:

        1
       / \
      /   \
     3     2
    / \   / \
   5   7 6   4

Сначала мы помещаем последний лист в корень:

Затем, поскольку он больше, чем оба его потомка, мы меняем его на наименьшего ребенка, который равен 2:

4 меньше, чем 6, поэтому мы останавливаемся.

5. Реализация сортировки кучи в Java

Со всем, что у нас есть, удаление корня (выскакивание) выглядит следующим образом:

class Heap> {

    // ...

    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> {

    // ...

    static > List sort(Iterable elements) {
        Heap heap = of(elements);

        List result = new ArrayList<>();

        while (!heap.isEmpty()) {
            result.add(heap.pop());
        }

        return result;
    }
    
    static > Heap of(Iterable elements) {
        Heap result = new Heap<>();
        for (E element : elements) {
            result.add(element);
        }
        return result;
    }
    
    // ...

}

Мы можем убедиться, что он работает со следующим тестом:

@Test
void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() {
    // given
    List elements = Arrays.asList(3, 5, 1, 4, 2);
    
    // when
    List 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% элементов находятся на двух самых нижних уровнях. Поэтому большинство операций вставки не займет больше двух шагов.

Обратите внимание, что в реальных данных быстрая сортировка обычно более эффективна, чем сортировка кучи. Серебряная подкладка заключается в том, что сортировка кучи всегда имеет наихудший случай O(n log n) временная сложность.

7. Заключение

В этом уроке мы увидели реализацию двоичной кучи и кучи.

Даже несмотря на то, что это время сложности O(n log n) в большинстве случаев это не лучший алгоритм для реальных данных.

Как обычно, примеры доступны на GitHub .