Обзор
Сортировка кучи - это сортировка выбора деревьев, которая является эффективным улучшением при сортировке прямого выбора.
Куча определяется следующим образом: последовательность n элементов (K1, K2, ..., KN), тогда и только тогда, когда удовлетворен:
В то время это называется кучей. Как видно из определения кучи, верхним элементом кучи (то есть первым элементом) должен быть наименьшим элементом (небольшая верхняя куча) или самый большой элемент (большая верхняя куча).
Если куча хранится в одномерном массиве, куча соответствует полностью двоичному дереву, а значения всех нелистых узлов (узлов с детьми) не больше (или не меньше, чем) значения их детей, а значения корневого узла (верхний элемент кучи) являются наименьшими (или самыми большими).
(а) Большая верхняя последовательность кучи: (96, 83, 27, 38, 11, 09)
(б) Небольшая последовательность верхней кучи: (12, 36, 24, 85, 47, 30, 53, 91)
Первоначально, последовательность чисел N, которые должны быть сортированы, рассматривается как двоичное дерево, хранящее последовательно (одномерное двоичное дерево хранения), отрегулируйте их порядок хранения, чтобы сделать его кучей, выводя верхний элемент кучи, чтобы получить самый маленький (или самый большой) элемент элементов N. Затем перенастройте оставшиеся элементы N-1, чтобы стать кучей, вывести верхний элемент кучи и получить элемент, который является вторым небольшим (или вторым большим) среди N-элементов. И так далее, пока вы, наконец, не получите упорядоченную последовательность с n узлами. Назовите эту кучу процесса.
Шаги и примеры
Есть две проблемы, которые необходимо решить при реализации сортировки кучи:
(1) как построить n чисел, чтобы сортироваться в свай;
(2) После вывода верхнего элемента кучи, как отрегулировать оставшиеся элементы N-1, чтобы сделать его новой кучей.
Построить метод кучи (небольшая верхняя куча):
Процесс создания кучи для начальной последовательности - это процесс повторного скрининга.
Полное двоичное дерево N узлов, затем последний узел является поддереем N/2 -го узла.
Фильтр начинается с поддерева с N/2 -м узлом в качестве корня (N/2 является последним узлом с поддереем), так что поддерек становится кучей.
Затем отфильтруйте подтереев с каждым узлом в качестве корня в последовательности вперед, чтобы сделать его кучей до корневого узла.
Как показано на рисунке, неупорядоченная последовательность начального процесса построения кучи: (49, 38, 65, 97, 76, 13, 27, 49)
(а) Неупорядоченная последовательность, начальное двоичное дерево, 97 (8/2 = 4 узел) - родительский узел последнего узла (49).
(b) 97> = 49, замените позицию, а затем отфильтруйте предыдущий узел 65 n/2.
(C) 13 <= 27 и 65> = 13, замените позиции 65 и 13, а затем замените 38 (оба больше, чем его, не требуется операция), фильтр 49.
(d) 13 <= 38 и 49> = 13, замените позиции 49 и 13, 49> = 27, замените позиции 49 и 27.
(e) Наконец -то получите кучу, 13 - минимальное число, которое мы получаем.
Методы регулировки кучи (небольшая верхняя куча):
Приводится куча элементов М. После вывода верхних элементов кучи остаются элементы M-1. Нижний элемент кучи питается в верхней части кучи, а куча уничтожается, потому что корневой узел не соответствует свойствам кучи.
Обменяйте корневой узел с меньшими элементами в левой и правой подтережах.
Если обменять с левым поддереем: если куча левого поддерева повторно, повторите метод (2).
Если обменять с правым поддереем, повторите метод (2), если правая куча поддерево уничтожена.
Продолжайте выполнять вышеупомянутую операцию обмена на подделки, которые не соответствуют свойствам кучи, пока не будут построены узлы листьев и кучу.
Чтобы отрегулировать кучу, вам нужно только рассмотреть поврежденные узлы, а другие узлы не нужно регулировать.
Реализация кода (Java)
Запустите код и сравните комментарии с приведенными выше примером шагов для сравнения.
Пакет com.coder4j.main; открытый класс Heapsort { / ** * Приспосабливается к небольшой верхней куче (результат от больших до маленького после сортировки) * * @param Массив - это массив кучи, который должен быть скорректирован * @param s - это положение элемента массива, чтобы быть отрегулированным * @param длина). tmp = массив [s]; int Child = 2 * S + 1; // Положение системы левого дочернего узла. В то время как (ребенок <длина) {// ребенок + 1 является правильным ребенком, в настоящее время корректирующий узел // Если есть правый ребенок, и он меньше левого ребенка, используйте правого ребенка, чтобы сравнить с узлом, в противном случае используйте левого ребенка, если (ребенок + 1 <длина && массив [ребенок]> массив [ребенок + 1]) {Child ++; } System.out.println ("будет с детской массивом [" + child + "] =" + массив [ребенок] + "compareare"); // Если меньший ребенок меньше этого узла if (массив [s]> массив [child]) {System.out.println («Ребенок меньше его, положения свопа»); Array [s] = массив [ребенок]; // переместить меньшего ребенка вверх и заменить текущий узел, который будет скорректирован S = ребенок; // переместить скорректированный узел в исходное положение массива младшего ребенка [Child] = TMP; child = 2 * s + 1; // продолжать судить о том, необходимо ли корректировать узел, чтобы продолжать регулироваться, если (ребенок> = длина) {System.out.println («Нет детей, корректировка закончена»); } else {System.out.println ("Продолжайте сравнивать с новым ребенком"); } // продолжать; } else {System.out.println («Дети старше их, корректировка окончена»); Break; // текущий узел, который должен быть скорректирован, меньше, чем его левый и правый детей, и его не нужно регулировать, выходите непосредственно}}/ ** * Настройка к большой верхней куче (результат от малого до большого после сортировки) * * @param Массив - это массив кучи, чтобы быть отрегулированным * @param s. aterle at @param @param @param labray labray labram day days lognay @param labram day day day day day day day day day day day day day day day day day day day day day day day. heapadjustb (int [] массив, int s, int length) {int tmp = массив [s]; int Child = 2 * S + 1; // Положение системы левого дочернего узла. В то время как (ребенок <длина) {// ребенок + 1 является правильным ребенком, в настоящее время корректирующий узел // Если есть правый ребенок, и он больше, чем левый ребенок, используйте правого ребенка, чтобы сравнить с узлом, в противном случае используйте левого ребенка, если (ребенок + 1 <длина && Array [Child] <Array [Child + 1]) {Child ++; } System.out.println ("будет с детской массивом [" + child + "] =" + массив [ребенок] + "compareare"); // Если пожилой ребенок больше этого узла, если (массив [s] <array [ребенок]) {System.out.println («Ребенок больше, чем он, положения свопа»); Array [s] = массив [ребенок]; // переместить ребенка вверх и заменить текущий узел, который будет скорректирован S = ребенок; // переместить скорректированный узел в исходное положение массива старшего возраста [Child] = TMP; child = 2 * s + 1; // продолжать судить о том, необходимо ли корректировать узел, который должен быть скорректирован, если (ребенок> = длина) {System.out.println («Нет детей, корректировка закончена»); } else {System.out.println ("Продолжайте сравнивать с новым ребенком"); } // продолжать; } else {System.out.println («Дети меньше их, корректировка закончилась»); break;// The current node to be adjusted is larger than its left and right children, and exit directly without adjustment} } } /** * Heap sorting algorithm * * @param array * @param inverse true In reverse order, false in positive order*/ public static void heapSort(int[] array, boolean inverse) { // Initial heap// The position of the last node with a child i = (length - 1) / 2, чтобы настроить каждый узел вверх, чтобы соответствовать системе кучи. for (int i = (array.length-1) / 2; i> = 0; i--) {if (обратный) {Heapadjusts (массив, i, array.length); } else {heapadjustb (массив, i, array.length); }} System.out.println ("Начальный конец кучи"); for (int i = array.length-1; i> 0; i--) {// обменивать верхний элемент кучи h [0] и последний элемент в куче int tmp = массив [i]; массив [i] = массив [0]; массив [0] = tmp; // После каждого обмена верхним элементом кучи и последнего элемента в куче куча необходимо отрегулировать, если (обратная) {Heapadjusts (массив, 0, i); } else {heapadjustb (массив, 0, i); }}} public static void main (string [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; Heapsort (массив, false); для (int i: array) {System.out.print (i + ""); }}}Результаты работы:
Узел, который должен быть скорректирован в начале начальной кучи: массив [3] = 97 Ребенок будет меньше с дочерним массивом [7] = 49 Ребенок меньше с ребенком, а узел, который должен быть скорректирован в конце адаптации: массив [2] = 65, ребенок меньше с ребенком [5] = 13 - это меньше ребенка, а у ребенка скорее адаптированный ребенок, а не в скорой адаптации. Массив [1] = 38 Ребенок больше с массивом детей [3] = 49 Ребенок больше с массивом ребенка [0] = 49 Ребенок меньше с массивом детей [2] = 13 У ребенка меньше с массивом ребенка [6] = 27. Ребенок меньше, чем обменная позиция, и в обменной позиции нет ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 97 Ребенок меньше ребенка. Ребенок меньше ребенка. Обменная позиция продолжает сравниваться с новым ребенком. Ребенок является массивом [6] = 49 Ребенок меньше, чем позиция обмена, и в обменной позиции нет ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 97 Ребенок меньше ребенка. Ребенок меньше ребенка. Ребенок меньше ребенка. Ребенок массив [1] = 38 Ребенок меньше ребенка. Ребенок массив [3] = 49 ребенок меньше ребенка. Ребенок меньше, чем позиция обмена. Узел, который должен быть скорректирован после корректировки: массив [0] = 65 Ребенок - массив [1] = 49 Ребенок меньше ребенка, и позиция обмена продолжает сравниваться с новым ребенком. Ребенок будет больше, чем у ребенка. Узел, который будет скорректирован после регулировки: массив [0] = 76 Ребенок больше, чем у ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 76 Ребенок меньше ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 49 Ребенок меньше ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 97 Ребенок меньше ребенка. Узел, который должен быть скорректирован после регулировки: массив [0] = 97 76 65 49 49 38 27 13
PS: разница между сортировкой кучи и прямой сортировкой вставки
В порядке прямого выбора, чтобы выбрать запись с наименьшим ключевым словом из R [1..n], необходимо выполнить сравнение N-1, а затем выберите запись с наименьшим ключевым словом в R [2..N], необходимо выполнить сравнения N-2. Фактически, в следующих сравнениях N-2 многие сравнения могли быть проведены в предыдущих сравнениях N-1, но поскольку эти результаты сравнения не были сохранены в предыдущем порядке, эти операции сравнения были повторены в течение следующего порядка.
Сортировка кучи может сэкономить часть результатов сравнения через структуру дерева, что может уменьшить количество сравнений.