1. Основные знания
То, что мы обычно называем кучей, относится к двоичной куче, которая также называется полным двоичным деревом или приблизительно полным бинарным деревом. Двоичная куча разделена на самую большую кучу и самую маленькую кучу.
Сортировка кучи относится к алгоритму сортировки, разработанным с использованием структуры данных кучи, которая является своего рода выбором сортировки. Вы можете быстро найти элементы указанного индекса, используя характеристики массива. Массивы могут напрямую получать элементы на основе индекса, а временная сложность - O (1), то есть константы, поэтому они чрезвычайно эффективны для приобретения стоимости.
Характеристики максимальной кучи следующие:
Характеристики минимальной кучи следующие:
2. Алгоритм думал
1. Алгоритм идея самой большой кучи:
Во-первых, начальный R [0… N-1] встроен в самую большую кучу. В настоящее время это неупорядоченная куча. Вершина кучи является самым большим элементом, а затем обменивается последняя запись R [N-1] неупорядоченной области. Это приводит к новой неупорядоченной области r [0… n-2] и упорядоченной области R [n-1] и удовлетворяет r [0… n-2] .keys ≤ r [n-1].
Поскольку первый r [0… n-2] не может удовлетворить свойства максимальной кучи после обмена, первый r [0… n-2] регулируется до максимальной кучи, пока не будет отрегулирован только последний элемент R [0].
После завершения максимальной кучи, это на самом деле восходящая последовательность. Каждый раз, когда корректируется куча, самый большой элемент получается, а затем обменивается с последним элементом тока. Следовательно, полученная последняя последовательность представляет собой восходящую последовательность.
2. Алгоритм идея о наименьшей куче:
Во-первых, начальный R [0… N-1] встроен в самую маленькую кучу. В настоящее время это неупорядоченная куча. Верховный элемент кучи-это самый маленький элемент, а затем обменивается верхним R [0] с последним R [N-1] неупорядоченной области, получая тем самым новую неупорядоченную кучу r [0… n-2] и упорядоченную кучу r [n-1] и удовлетворяющую r [0… n-2] .keys> = r [n-1].
Поскольку первый r [0… n-2] может не соответствовать свойствам минимальной кучи после обмена, первый r [0… n-2] регулируется на минимальную кучу до тех пор, пока не будет отрегулирован только последний элемент R [0], а минимальная куча не будет сортирована. После того, как упорядочение минимальной кучи завершено, на самом деле это нисходящая последовательность. Каждый раз, когда корректируется куча, получается наименьший элемент и затем обменивается с последним элементом тока неупорядоченной кучи, поэтому полученная последовательность находится в порядке убывания.
Совет: процесс сортировки кучи фактически является процессом постоянного расширения упорядоченной области, а затем постоянно уменьшать неупорядоченную область до тех пор, пока не будут упорядоченные участки.
3. Анализ процесса сортировки
Поскольку алгоритм относительно абстрактный, здесь мы напрямую иллюстрируем процесс сортировки кучи, приводя небольшой пример. Далее мы используем эту неупорядоченную последовательность для использования самой большой кучи для сортировки кучи, а результирующая последовательность - восходящая последовательность (ASC).
Неупорядоченная последовательность: 89, -7,999, -89,7,0, -888,7, -7
Шаг 1: Инициализируйте максимальную кучу для построения:
Шаг 2: обменяйте максимальный элемент 999 в верхней части кучи с последним элементом неупорядоченной области, чтобы 999 стал упорядоченной областью. После обмена -7 становится верхней частью кучи. Поскольку -7 не является самым большим элементом в неупорядоченной области, необходимо регулировать неупорядоченную область, чтобы максимальное значение 89 в неупорядоченной области становилось верхней частью кучи, так что -7 и 89 обмениваются. После обмена правое поддерево 89 не соответствует свойствам самой большой кучи, поэтому правая поддерево должна быть отрегулирована до самой большой кучи, поэтому -7 необходимо обменять с 0, как показано на рисунке ниже:
Из рисунка, когда -7% 89% обмен, верхняя часть кучи является самым большим элементом, но левый ребенок -7 равен 0, а правый ребенок --888. Поскольку -7 <0 узел -7 не соответствует свойствам кучи, поэтому его необходимо скорректировать. Итак, 0 обменяется с -7.
Затем повторите второй шаг, пока он не станет упорядоченной областью.
Наконец: то, что получено, является восходящей последовательности
4. Временная сложность
Время сортировки кучи в основном состоит из временных накладных расходов на установление начальной кучи и неоднократно регулировки кучи. Поскольку сортировка кучи нестабильна, сложности, которую она получает, будет больше в соответствии с фактической ситуацией, поэтому она может занять только среднюю сложность времени.
Средняя сложность времени: O (n * log2 (n))
Отражившие много времени операции сортировки кучи включают: начальную кучу + повторную регулировку кучи, а сложность времени заключается в следующем:
1. Начальное здание кучи. Каждый родительский узел будет сравнивать и обмениваться с левыми и правыми узлами дочерних узлов до 2 раза, поэтому сложность связана с количеством родительских узлов. На основе 2x <= n (x - это количество раз, когда n элементы могут быть сложены пополам, то есть количество родительских узлов), он получает x = log2n. То есть o (log2n)
2. Повторная регулировка кучи: поскольку результаты сравнения массива записываются во время инициализации кучи, сортировка кучи не чувствительна к порядку массива исходной последовательности, и лучшая ситуация аналогична наихудшему случаю. Верхний элемент кучи должен быть извлечен N-1 раз. Каждый раз, когда получается верхний элемент кучи, необходимо восстановить кучу (O (Reconsuct Heap) <O (начальная куча)). Так что меньше, чем O (n-1) * o (log2n)
Рекомендуемое использование:
Поскольку количество раз инициализации кучи необходимо сравнить, сортировка кучи более подходит для ситуаций, когда объем данных очень большой (миллион данных или более). Поскольку эффективная быстрая сортировка основана на рекурсивной реализации, ошибка переполнения стека возникает, когда объем данных очень большой.
5. Пример кода Java
Общедоступный класс heapsort {private static int [] sort = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (string [] args) {buildmaxHeapify (sort); Heapsort (Sort); print (sort); } private static void buildmaxHeapify (int [] data) {// Только те, у кого нет детей, необходимо создать максимальную кучу, запустите с последнего родительского узла int startIndex = getParentIndex (data.length-1); // Создать максимальную кучу с конца, и это правильная куча для (int i = startIndex; i> = 0; i-) {max-max (dtaify; }}/***Создать максимальную кучу**@paramdata*@paramheapsize требует размер максимальной кучи, которая обычно используется в сортировке, поскольку максимальное значение размещается в конце, конечный конец больше не классифицируется как максимальная куча*@paramindex, в которой максимальная куча в настоящее время*/private void maxheapif текущая точка с левым и правым узлами дочерних узлов int left = getChildleftIndex (index); int right = getChildrightIndex (index); int самый большой = индекс; if (слева <heApsize && data [index] <data [Left]) {самый большой = оставленный; } if (right <heApsize && data [самый большой] <data [right]) {самый большой = справа; } // После получения максимального значения это может потребоваться обменять. В случае обмена его дети не могут быть самой большой кучей. Это необходимо перенаправить, если (самый большой! = Index) {int temp = data [index]; Данные [index] = данные [самый большой]; Данные [самый большой] = темп; maxheapify (данные, Heapize, самый большой); }} /***Сортировка, максимальное значение помещается в конце. Хотя данные являются самой большой кучей, она становится постепенной после сортировки * *@paramdata */private static void huepsort (int [] data) {// обмен с заголовком в конце, отрегулируйте максимальную кучу после обмена на (int i = data.length-1; i> 0; i-) {int temp = data [0]; DATA [0] = DATA [i]; data [i] = temp; maxheapify (данные, i, 0); }} / ** *paramcurrent *@return * / private int int getParentIndex (int current) {return (current-1) >> 1; } / ** *Настоящая позиция узела дочернего узела Обратите внимание на скобки, а приоритет добавления выше * *@paramcurrent *@return * / private static int getChildleftIndex (int current) {return (current << 1) +1; } / ** *Правая позиция детского узла * *@paramcurrent *@return * / private static int getChildrightIndex (int current) {return (current << 1) +2; } private static void print (int [] data) {int pre = -2; for (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } System.out.print (data [i]+"|"); }}/** *Логотип с базой 2 * *@paraparam *@return */private static double getLog (double param) {return math.log (param) /math.log (2); }}