В школе мы в настоящее время изучаем алгоритмы сортировки на Java, и я получил для своей домашней работы кучу сортировки. Я сделал свое чтение, я пытался выяснить, насколько мог, но, похоже, я просто не могу понять концепцию.
Я не прошу вас написать мне программу на Java, если бы вы могли просто объяснить мне так же просто, как вы можете, как работает сортировка кучи.
Правильно, так что в основном вы берете кучу и вытаскиваете первый node в кучу - поскольку первый node гарантированно будет самым большим/наименьшим в зависимости от направления сортировки. Трудная вещь заключается в повторной балансировке/создании кучи в первую очередь.
Мне понадобилось два шага, чтобы понять процесс кучи - прежде всего, думая об этом как о дереве, обнимая его вокруг, а затем превращаю это дерево в массив, чтобы он мог быть полезным.
Вторая часть состоит в том, чтобы по существу пересечь ширину дерева сначала, слева направо, добавляя каждый элемент в массив. Итак, следующее дерево:
73
7 12
2 4 9 10
1
Было бы {73,7,12,2,4,9,10,1}
Первая часть требует двух шагов:
Итак, чтобы собрать список чисел, которые вы добавляете в кучу, выполните следующие два шага.
Чтобы создать мою кучу выше, я добавлю 10 первых - это единственный node, поэтому ничего не делать. Добавьте 12, когда он находится слева:
10
12
Это удовлетворяет 1, но не 2, поэтому я поменяю их:
12
10
Добавить 7 - ничего не делать
12
10 7
Добавить 73
12
10 7
73
10 < 73, поэтому их нужно поменять:
12
73 7
10
12 < 73, поэтому их нужно поменять:
73
12 7
10
Добавить 2 - ничего не делать
73
12 7
10 2
Добавить 4 - ничего не делать
73
12 7
10 2 4
Добавить 9
73
12 7
10 2 4 9
7 < 9 - своп
73
12 9
10 2 4 7
Добавить 1 - ничего не делать
73
12 9
10 2 4 7
1
У нас есть куча: D
Теперь вы просто удаляете каждый элемент сверху, каждый раз заменяя последний элемент на вершину дерева, а затем повторно балансируя дерево:
Возьмите 73 - положите 1 на место
1
12 9
10 2 4 7
1 < 12 - замените их
12
1 9
10 2 4 7
1 < 10 - замените их
12
10 9
1 2 4 7
Возьмите 12 прочь - замените на 7
7
10 9
1 2 4
7 < 10 - обменять их
10
7 9
1 2 4
Возьмите 10 выкл. - замените на 4
4
7 9
1 2
4 < 7 - своп
7
4 9
1 2
7 < 9 - своп
9
4 7
1 2
Возьмите 9 выкл. - замените на 2
2
4 7
1
2 < 4 - обменять их
4
2 7
1
4 < 7 - обменять их
7
2 4
1
Возьмите 7 выкл. - замените на 1
1
2 4
1 < 4 - обменять их
4
2 1
Возьмите 4 - замените на 1
1
2
1 < 2 - обменять их
2
1
Возьмите 2 - замените на 1
1
Возьмите 1
Отсортированный список вуаля.
Один из способов думать о сортировке кучи - это умная оптимизированная версия выбора. В сортировке сортировки сортировка выполняется путем многократного поиска самого большого элемента, который еще не установлен правильно, а затем помещает его в следующее правильное место в массиве. Однако сортировка выбора выполняется во времени O (n 2), поскольку она должна выполнять n раундов нахождения самого большого элемента из группы (и может быть до n разных элементов, на которые нужно смотреть) и положив его на место.
Интуитивно, куча сортировки работает, создавая специальную структуру данных, называемую двоичную кучу, которая ускоряет поиск самого большого элемента из незанятого элементы массива. Двоичные кучи поддерживают следующие операции:
На очень высоком уровне алгоритм работает следующим образом:
Сортирует массив, потому что элементы, возвращаемые Удалить-Макс, находятся в порядке убывания. После удаления всех элементов массив затем сортируется.
Сортировка кучи эффективна, потому что операции Вставить и Удалить-Макс в куче работают в режиме O (log n), что означает, что n вставок и удалений может быть выполняется в куче в O (n log n) времени. Более точный анализ может быть использован, чтобы показать, что на самом деле он принимает время & theta; (n log n) независимо от входного массива.
Как правило, сортировка кучи использует две основные оптимизации. Во-первых, куча обычно создается внутри массива, обрабатывая сам массив как сжатое представление кучи. Если вы посмотрите на реализацию heapsort, вы обычно увидите необычное использование индексов массива на основе умножения и деления на два; эти обращения работают, потому что они обрабатывают массив как сжатую структуру данных. В результате для этого алгоритма требуется только O (1) вспомогательное пространство для хранения.
Во-вторых, вместо того, чтобы накапливать кучу по одному элементу за раз, куча обычно строится с использованием специализированного алгоритма, который выполняется во времени & Theta; (n) до постройте кучу на месте. Интересно, что в некоторых случаях это приводит к тому, что код легче читать, поскольку код можно повторно использовать, но сам алгоритм становится немного сложнее понять и проанализировать.
Иногда вы увидите, что heapsort сделан с тернарной кучей. Преимущество этого заключается в том, что в среднем оно немного быстрее, но если вы обнаружите, что реализация heapsort с использованием этого, не зная, что вы смотрите на него, может быть довольно сложной для чтения. Другие алгоритмы также используют одну и ту же общую структуру, но более сложную структуру кучи. Smoothsort использует гораздо более сложную кучу для получения наилучшего поведения O (n) при сохранении использования O (1) и O ( n log n) худшее поведение. Сорт тополя похож на smoothsort, но с использованием пространства O (log n) и немного лучшей производительностью. Можно даже подумать о классических алгоритмах сортировки, таких как сортировка сортировки и сортировка вставки как варианты сортировки кучи.
Как только у вас будет лучшее понимание heapsort, вы можете захотеть изучить алгоритм introsort, который объединяет quicksort, heapsort, и сортировку вставки для создания чрезвычайно быстрого алгоритма сортировки, который сочетает в себе силу быстрой сортировки (быстрая сортировка в среднем), heapsort (превосходное поведение в худшем случае) и сортировка вставки (быстрая сортировка для небольших массивов). Introsort - это то, что используется во многих реализациях функции С++ std::sort, и не очень сложно реализовать себя, когда у вас есть рабочий сервер.
Надеюсь, это поможет!
Предположим, что у вас есть специальная структура данных (называемая кучей), которая позволяет вам хранить список чисел и позволяет вам извлекать и удалять наименьшее число в O(lg n).
Вы видите, как это приводит к очень простому алгоритму сортировки?
Жесткая часть (на самом деле это не так сложно) реализует кучу.
Я помню, как мой профессор по анализу алгоритмов сказал нам, что алгоритм сортировки кучи работает как куча гравия:
Представьте, что у вас есть мешок, заполненный гравий, и вы опорожните его на полу: более крупные камни, скорее всего, катятся на дно, а маленькие камни (или песок) будут оставаться на вершине.
Теперь вы берете верхнюю часть кучи и сохраняете ее при наименьшем значении вашей кучи. Положите оставшуюся часть своей кучи в свой мешок и повторите. (Или вы можете получить противоположный подход и захватить самый большой камень, который вы видели на полу, пример по-прежнему действителен)
Это более или менее простой способ узнать, как работает сортировка кучи.
Возможно, интерактивная трассировка поможет вам лучше понять алгоритм. Вот демон .
Я посмотрю, как я отвечаю на это, потому что мое объяснение сортировки кучи и какая куча будет немного...
... мм, ужасно.
Во всяком случае, во-первых, нам лучше проверить, что такое куча:
Как взято из Wikipedia, куча:
В информатике куча представляет собой специализированную древовидную структуру данных, которая удовлетворяет свойству кучи: если B является дочерним node A, тогда клавиша (A) ≥ (B). Это означает, что элемент с наибольшим ключом всегда находится в корне node, и поэтому такая куча иногда называется max-heap. (В противном случае, если сравнение отменено, наименьший элемент всегда находится в корне node, что приводит к мини-куче.)
В значительной степени куча является бинарным деревом, так что все дочерние элементы любого node меньше, чем node.
Теперь сортировка кучи - это алгоритм сортировки O (n lg (n)). Вы можете немного прочитать об этом здесь и здесь. Это в значительной степени работает, поместив все элементы того, что вы пытаетесь сортировать в кучу, а затем построите отсортированный массив от самого большого элемента до самого маленького. Вы будете продолжать реструктурировать кучу, и поскольку самый большой элемент находится наверху (корневой) кучи во все времена, вы можете просто продолжать использовать этот элемент и помещать его в конец отсортированного массива. (То есть вы построите отсортированный массив в обратном порядке)
Почему этот алгоритм O (n lg (n))? Поскольку все операции над кучей - это O (lg (n)), и в результате вы будете выполнять n операций, в результате чего общее время работы O (n lg (n)).
Я надеюсь, что моя страшная просьба помогла вам! Это немного многословие; извините за это...
Сортировка кучи включает простейшую логику с временной сложностью O (nlogn) и сложностью пространства O (1)
public class HeapSort {
public static void main(String[] args) {
Integer [] a={12,32,33,8,54,34,35,26,43,88,45};
HeapS(a,a.length-1);
System.out.println(Arrays.asList(a));
}
private static void HeapS(Integer[] a, int l) {
if(l<=0)
return;
for (int i = l/2-1; i >=0 ; i--) {
int index=a[2*i+1]>a[2*i+2]?2*i+1:2*i+2;
if(a[index]>a[i]){
int temp=a[index];
a[index]=a[i];
a[i]=temp;
}
}
int temp=a[l];
a[l]=a[0];
a[0]=temp;
HeapS(a,l-1);
}
}