Сортировка кучи в Java
В этом уроке мы увидим, как работает Heap Sort, и реализуем его на Java.
- Сортировка кучи основана на структуре данных кучи. ** Чтобы правильно понять сортировку кучи, сначала мы рассмотрим кучи и способы их реализации.
2. Структура данных кучи
Куча — это специализированная древовидная структура данных . Поэтому он состоит из узлов. Мы присваиваем элементы узлам: каждый узел содержит ровно один элемент.
Также узлы могут иметь детей. Если у узла нет дочерних элементов, мы называем это листом.
Что делает Heap особенным, так это две вещи:
, значение каждого узла должно быть ** меньше или равно всем значениям, хранящимся в его
дети , это полное дерево ** , что означает, что оно имеет наименьшую возможную высоту
Из-за 1-го правила наименьший элемент всегда будет в корне дерева .
То, как мы применяем эти правила, зависит от реализации.
Кучи обычно используются для реализации очередей с приоритетами, поскольку кучи — очень эффективная реализация извлечения наименьшего (или наибольшего) элемента.
2.1. Куча вариантов
Куча имеет много вариантов, все они отличаются некоторыми деталями реализации.
Например, то, что мы описали выше, это Min-Heap, потому что родитель всегда меньше, чем все его дочерние элементы . В качестве альтернативы, мы могли бы определить Max-Heap, в этом случае родитель всегда больше, чем его дети. Следовательно, наибольший элемент будет в корневом узле.
Мы можем выбрать из множества реализаций дерева. Самым простым является Бинарное Дерево. В двоичном дереве каждый узел может иметь не более двух дочерних элементов. Мы называем их левым потомком и правым потомком
Самый простой способ обеспечить соблюдение второго правила — использовать полное двоичное дерево. Полное двоичное дерево следует нескольким простым правилам:
, если у узла есть только один дочерний элемент, это должен быть его левый дочерний элемент
, только самый правый узел на самом глубоком уровне может иметь ровно один
ребенок , листья могут быть только на самом глубоком уровне
Давайте посмотрим на эти правила на нескольких примерах:
Деревья 1, 2, 4, 5 и 7 следуют правилам.
Дерево 3 и 6 нарушают 1-е правило, 8 и 9 — 2-е правило, а 10 — 3-е правило
В этом уроке мы сосредоточимся на Min-Heap с реализацией Binary Tree .
2.2. Вставка элементов
Мы должны реализовать все операции таким образом, чтобы они сохраняли инварианты кучи. Таким образом, мы можем построить Heap с повторными вставками , поэтому мы сосредоточимся на одной операции вставки.
Мы можем вставить элемент с помощью следующих шагов:
, создать новый лист, который является самым правым доступным слотом на самом глубоком
выровнять и сохранить элемент в этом узле , если элемент меньше родительского, мы меняем их местами
, продолжайте с шага 2, пока элемент не станет меньше, чем его родитель или
Обратите внимание, что шаг 2 не будет нарушать правило кучи, потому что если мы заменим значение узла на меньшее, оно все равно будет меньше, чем его дочерние элементы.
Давайте посмотрим на пример! Мы хотим вставить 4 в эту кучу:
Первым шагом является создание нового листа, который хранит 4:
Поскольку 4 меньше, чем его родитель, 6, мы меняем их:
Теперь мы проверяем, меньше ли 4, чем его родитель, или нет. Поскольку его родитель равен 2, мы останавливаемся. Куча все еще в силе, и мы вставили номер 4.
Мы должны поменять местами 1 и 4:
Теперь мы должны поменять местами 1 и 2:
Так как 1 новый корень, мы остановимся.
3. Реализация кучи в Java
Поскольку мы используем Full Binary Tree, мы можем реализовать его с массивом : элемент в массиве будет узлом в дереве. Мы помечаем каждый узел индексами массива слева направо, сверху вниз следующим образом:
Единственное, что нам нужно, это отслеживать, сколько элементов мы храним в дереве. Таким образом, индекс следующего элемента, который мы хотим вставить, будет размером массива.
Используя эту индексацию, мы можем вычислить индекс родительского и дочернего узлов:
Поскольку мы не хотим беспокоиться о перераспределении массива, мы еще больше упростим реализацию и будем использовать ArrayList .
Базовая реализация двоичного дерева выглядит следующим образом:
class BinaryTree < Listelements = 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.Comparable .
4. Сортировка кучи
Поскольку корень кучи всегда содержит наименьший элемент, идея сортировки кучи довольно проста: удаляйте корневой узел, пока куча не станет пустой .
Единственное, что нам нужно, это операция удаления, которая поддерживает кучу в согласованном состоянии. Мы должны убедиться, что мы не нарушаем структуру двоичного дерева или свойства кучи.
- Чтобы сохранить структуру, мы не можем удалить любой элемент, кроме самого правого листа. ** Поэтому идея состоит в том, чтобы удалить элемент из корневого узла и сохранить самый правый лист в корневом узле.
Но эта операция наверняка нарушит свойство Heap. Так что если новый корень больше, чем любой из его дочерних узлов, мы поменяем его на его наименее дочерний узел Поскольку наименьший дочерний узел меньше всех других дочерних узлов, он не нарушает свойство Heap.
Мы продолжаем менять местами, пока элемент не станет листом, или он станет меньше всех его дочерних элементов
Давайте удалим корень из этого дерева:
Сначала мы помещаем последний лист в корень:
Затем, поскольку он больше, чем оба его потомка, мы меняем его на наименьший дочерний элемент, равный 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) < Heapheap = of(elements); List result = new ArrayList<>(); while (!heap.isEmpty()) < result.add(heap.pop()); >return result; > static > Heap of(Iterable elements) < Heapresult = new Heap<>(); for (E element : elements) < result.add(element); >return result; > //. >Мы можем убедиться, что он работает с помощью следующего теста:
@Test void givenNotEmptyIterable__whenSortCalled__thenItShouldReturnElementsInSortedList() < //given Listelements = 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) .
Обратите внимание, что мы не упомянули стоимость перераспределения массива, но, поскольку это O (n) , это не влияет на общую сложность. Также, как мы упоминали ранее, можно реализовать сортировку на месте, что означает, что перераспределение массива не требуется.
Также стоит отметить, что 50% элементов — это листья, а 75% элементов находятся на двух самых нижних уровнях. Поэтому большинство операций вставки не займет больше, чем два шага.
- Обратите внимание, что в реальных данных Quicksort обычно более производительный, чем Heap Sort. Серебряная подкладка состоит в том, что сортировка кучи всегда имеет наихудший случай O (n log n) сложность времени. **
7. Заключение
В этом уроке мы увидели реализацию Binary Heap и Heap Sort.
- Хотя сложность по времени равна O (n log n) , в большинстве случаев это не лучший алгоритм для реальных данных.
Как обычно, примеры доступны по адресу over на GitHub .
Heap sort in java
A heap is a tree with some special properties, so value of node should be greater than or equal to(less than or equal to in case of min heap) children of the node and tree should be complete binary tree.
Binary heaps
Binary heaps are those heaps which can have up to 2 children. We will use binary heaps in our next few sections.
Understanding complete binary tree
Complete binary tree is a binary tree whose leaves are at h or h-1 level where h is height of the tree.
Index of left child= 2*(index of its parent)+1
Index of right child= 2*(index of its parent)+2
Types of heaps
Max heap : It is binary heap where value of node is greater than left and right child of the node.
Min heap : It is binary heap where value of node is lesser than left and right child of the node.
Heapifying an element:
Once we create a heap , it may not satisfy heap property. In order to make it heap again, we need to adjust locations of the heap and this process is known as heapifying the elements.
In order to create a max heap, we will compare current element with its children and find the maximum, if current element is not maximum then exchange it with maximum of left or right child.
Java code for heapifying element at location i :