Сортировка кучей в Java

Существует множество алгоритмов, позволяющих эффективно сортировать элементы, но в этом руководстве мы рассмотрим, как реализовать пирамидальную сортировку в Java.

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

Мы будем делать другую реализацию без кучи — а скорее PriorityQueue s, которая сводит алгоритм к одной строке .

Куча как структура данных

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

В максимальной куче для данного родительского элемента P и дочернего элемента C значение P больше или равно значению дочернего элемента C.

Аналогично, в минимальной куче значение P меньше или равно значению его дочернего элемента C. Узел на «верху» кучи (т. е. узел, у которого нет родителей) называется корнем.

Вот пример минимальной кучи (слева) и максимальной кучи (справа):

Как мы упоминали ранее, мы рассматриваем кучу как древовидную структуру данных. Однако мы представим его в виде простого массива и просто определим, как каждый узел (дочерний элемент) связан со своим родителем. Предполагая, что наш массив начинается с индекса 0, мы можем представить максимальную кучу из рисунка выше с помощью следующего массива:

53, 25, 41, 12, 6, 31, 18

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

Для k-th элемента массива мы можем найти его дочерние элементы по позициям 2*k+1и 2*k+2, предполагая, что индексация начинается с 0. Аналогично мы можем найти родителя элемента k-thпо позиции (k-1)/2.

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

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

Чтобы подробнее объяснить концепцию полного двоичного дерева, давайте посмотрим на пример максимальной кучи из иллюстрации ранее. Если удалить узлы 12, то 6получим следующее двоичное дерево:

Это дерево будет представлено в виде массива:

53, 25, 41, -, -, 31, 18

Мы видим, что это не полное двоичное дерево, поскольку узлы на уровне 2(если корневой узел находится на уровне 0) не выровнены по левому краю. С другой стороны, следующее двоичное дерево будет представлять собой полное двоичное дерево:

Массив для этого дерева будет:

53, 25, 41, 12, 6

Из приведенного выше короткого примера мы видим, что интуитивно полное двоичное дерево представляется массивом, в котором нет «пробелов», то есть позиций, которые мы представили в первом массиве выше как -.

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

Примечание. Мы сосредоточимся на максимальной куче, но имейте в виду, что все, что применимо к максимальной куче, также применимо и к минимальной куче.

Вставка элемента в максимальную кучу

Используя ту же максимальную кучу, которую мы использовали ранее, допустим, мы хотим добавить element 60. На первый взгляд очевидно, что это 60будет самый большой элемент в нашей куче, поэтому он должен стать корневым элементом. Но тут возникает другой вопрос: как нам одновременно сохранять форму полного двоичного дерева и 60одновременно складывать?

Начнем с размещения элемента в последней позиции нашего массива кучи и получим что-то вроде этого:

// 0   1   2   3  4   5   6   7
  53, 25, 41, 12, 6, 31, 18, 60

Числа в строке выше представляют индексные позиции массива.

Как обсуждалось ранее, дочерние k-th злы расположены в позициях 2*k+1и 2*k+2, а родительский узел каждого узла находится в позициях (k-1)/2. Следуя тому же шаблону, 60будет дочерним элементом 12.

Теперь это нарушает форму нашей максимальной кучи, поскольку сравнение и проверка, 60меньше или равно, 12 дает отрицательный ответ. Что мы сделаем, так это поменяем местами60 эти два числа, так как мы уверены, что в двоичном дереве нет меньших чисел , чем 60в листе.

После замены получаем следующее:

// 0   1   2   3  4   5   6   7
  53, 25, 41, 60, 6, 31, 18, 12

Повторяем тот же шаг, что и раньше, пока 60 не окажется в нужном месте. Родительский элемент 60 теперь будет 25. Мы меняем эти два места, после чего родительский элемент 60 is 53, после чего мы также меняем их местами, в результате чего получается максимальная куча:

// 0   1   2   3  4   5   6   7
  60, 53, 41, 25, 6, 31, 18, 12

Удаление элемента из максимальной кучи

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

максимальной кучи это самый большой элемент, а в случае минимальной кучи — наименьший.

Удалить элемент из кучи так же просто, как удалить его из массива. Однако это создает новую проблему, поскольку удаление создает «пробел» в нашем двоичном дереве, делая его неполным.

К счастью для нас, решение столь же простое — мы заменяем удаленный корневой элемент элементом, который находится в самом правом углу на самом нижнем уровне кучи. Это гарантирует нам, что мы снова получим полное двоичное дерево, но снова создает новую потенциальную проблему: хотя наше двоичное дерево теперь завершено, оно может не быть кучей. Итак, как нам решить эту проблему?

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

// 0   1   2   3  4   5  6
  18, 25, 41, 12, 6, 31

Примечание. Элемент в позиции 6 намеренно оставлен пустым — это будет важно позже.

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

После этого мы получим следующий массив:

// 0   1   2   3  4   5  6
  41, 25, 18, 12, 6, 31

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

// 0   1   2   3  4   5  6  41, 25, 31, 12, 6, 18

И вот так у нас снова макс куча!

Временная сложность вставки и удаления

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

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

На этом мы завершаем объяснение кучи как структуры данных и переходим к основной теме статьи — пирамидальной сортировке .

Сортировка кучей в Java

Воспользовавшись преимуществами кучи и ее свойств, мы выразили ее как массив. Мы можем так же легко максимально увеличить кучу любого массива. Max heapify -ing — это процесс расположения элементов в правильном порядке, чтобы они соответствовали свойству max heap. Точно так же вы можете минимизировать кучу массива.

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

Давайте посмотрим на следующий массив:

// 0   1  2   3   4   5   6  
   25, 12, 6, 41, 18, 31, 53

Давайте быстро пропустим через него алгоритм heapify и вручную создадим кучу из этого массива, а затем реализуем код на Java, который сделает это за нас. Начинаем справа и идем до упора налево:

25 12 *6* 41 18 **31** **53** 

Поскольку оба 31 > 6и 53 > 6, мы берем больший из двух (в данном случае 53) и меняем его местами с родительским, и получаем следующее: 25 12 53 41 18 31 6 .

25 *12* 6 **41** **18** 31 6 

Еще раз, 18 > 12и 41 > 12, и поскольку 41 > 18, меняем местами 42и 12.

*25*, **41**, **53** 12, 18, 31, 6 

На этом последнем этапе мы видим, что 41 > 25и 53 > 25, и поскольку 53 > 41, мы меняем местами 53и 25. После этого мы рекурсивно собираем в кучу файлы 25.

53, 41, *25*, 12, 18, **31**, **6** 

31 > 25, поэтому мы меняем их местами.

53, 41, 31, 12, 18, 25, 6 

У нас есть максимальная куча! Однако этот процесс может показаться устрашающим — при реализации в коде он на самом деле довольно прост. Процесс «кучи» имеет решающее значение для пирамидальной сортировки, которая состоит из трех этапов:

1. Создайте массив максимальной кучи, используя входной массив.
2. Поскольку максимальная куча хранит наверху самый большой элемент массива (то есть начало массива), нам нужно поменять его местами с последним элементом внутри массива с последующим уменьшением размера массива (кучи ) по 1. После этого «кучиваем» корень.
3. Повторяем шаг 2 до тех пор, пока размер нашей кучи больше 1.

Имея хорошее представление о том, как работает алгоритм, мы можем приступить к его реализации. Обычно, поскольку мы будем вызывать heapify()метод несколько раз, мы реализуем его отдельно от heapsort()метода и вызываем внутри него.

Это делает реализацию более понятной и легкой для чтения. Начнем с heapify()метода:

public static void heapify(int[] array, int length, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < length && array[left] > array[largest]) {
        largest = left;
    }
    if (right < length && array[right] > array[largest]) {
        largest = right;
    }
    if (largest != i) {
        int tmp = array[i];
        array[i] = array[largest];
        array[largest] = tmp;
        heapify(array, length, largest);
    }
}

Метод heapify()выполняет большую часть тяжелой работы и состоит всего из трех ifоператоров. Сам алгоритм пирамидальной сортировки также довольно прост и в основном опирается на heapify():

public static void heapSort(int[] array) {
    if (array.length == 0) {
        return;
    }
    
    int length = array.length;
    
    // Moving from the first element that isn't a leaf towards the root
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
    
    for (int i = length - 1; i >= 0; i--) {
        int tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        heapify(array, i, 0);
    }
}

Вот и все! Теперь мы можем передать массив методу heapSort(), который сортирует его на месте:

public static void main(String[] args){
    int[] array = {25, 12, 6, 41, 18, 31, 53};
    heapSort(array);
    System.out.println(Arrays.toString(array));
}

Это приводит к:

[6, 12, 18, 25, 31, 41, 53]

Реализация пирамидальной сортировки с приоритетной очередью

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

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

PriorityQueueВ пакете Java есть встроенная функция util:

import java.util.PriorityQueue;

У него PriorityQueueдовольно много собственных и унаследованных от интерфейса методов Queue, но для наших целей нам понадобится использовать лишь несколько:

• boolean add(E e)— вставляет элемент eв приоритетную очередь.
• E poll()— извлекает и удаляет заголовок приоритетной очереди или возвращает, nullесли она пуста.
• int size()— возвращает количество элементов в приоритетной очереди.

С их помощью мы действительно можем реализовать пирамидальную сортировку с помощью одного while()цикла .

Прежде всего, мы создадим и добавим элементы в очередь приоритетов, после чего просто запускаем цикл whileдо тех пор, пока в нашей очереди приоритетов pqесть хотя бы 1элемент. На каждой итерации мы используем этот poll()метод для получения и удаления заголовка очереди, после чего распечатываем его и выдаем тот же результат, что и раньше:

Queue<Integer> pq = new PriorityQueue<>();
int[] array = new int[]{25, 12, 6, 41, 18, 31, 53};
Arrays.stream(array).forEach(element -> pq.add(element));

while(pq.size() > 0){
    System.out.print(pq.poll() + " ");
}

Это приводит к:

6 12 18 25 31 41 53 

Временная сложность пирамидальной сортировки

Давайте обсудим временную сложность обоих рассмотренных нами подходов.

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

А как насчет космической сложности? Что ж, поскольку в обоих подходах мы используем только начальный массив для сортировки массива, это означает, что дополнительное пространство, необходимое для пирамидальной сортировки, составляет , что O(1)делает пирамидальную сортировку алгоритмом на месте.

Заключение

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

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