1. Введение в сортировку кучей
Источник Энциклопедия Baidu:
Heapsort (Heapsort) относится к алгоритму сортировки, разработанному с использованием структуры данных стекового дерева (кучи), что является разновидностью сортировки выбором. Вы можете использовать характеристики массива, чтобы быстро найти элемент по указанному индексу. Куча делится на большую корневую кучу и маленькую корневую кучу, даполное бинарное дерево.
У меня уже есть статья о введении бинарных деревьев.В то время я объяснял бинарное дерево поиска.Каким бинарным деревом является упомянутое выше полное бинарное дерево? ? А какое бинарное дерево является полным бинарным деревом? ? Существует ли вообще полное бинарное дерево? ?
- Полное бинарное дерево: каждый слой, кроме последнего, полностью заполнен, и все узлы остаютсяВыровнять по левому краю.
- Полное бинарное дерево: у каждого узла, кроме листовых, есть два потомка,Каждый слой (включая последний, конечно) полностью заполнен.
- Полное бинарное дерево:Каждый узел, кроме листовых узлов, имеет два дочерних узла.
Вот картинка для разговора:
- Полное бинарное дерево:
- Идеальное бинарное дерево:
- Полное бинарное дерево:
Использованная литература:
Проще говоря:Сортировка кучей — это алгоритм, который обрабатывает данные как полное бинарное дерево и сортирует их в соответствии с характеристиками полного бинарного дерева.
- Максимальная куча требует, чтобы элементы узла были не меньше, чем его дочерние элементы, а минимальная куча требует, чтобы элементы узла были не больше, чем его левый и правый дочерние элементы.
- Тогда элемент в корневом узле максимальной кучи должен иметь максимальное значение в куче.
Здесь мы обсуждаеммаксимумкуча:В настоящее время каждый родительский узел больше дочернего узла
Полное бинарное дерево обладает следующими свойствами:左边子节点位置 = 当前父节点的两倍 + 1,右边子节点位置 = 当前父节点的两倍 + 2
Во-вторых, опыт сортировки кучи
Теперь у нас есть полное бинарное дерево: и левое, и правое поддерево соответствуют максимальной куче -->父>子
Но мы обнаружим, что номер корневого элемента не совпадает, очевидно, что:1 меньше 7
Обменяем, а после обмена найдем:Правое поддерево снова не совпадает~
Потому что правое поддерево становится таким:
Наконец, мыПоменять местами максимальное значение правого поддерева на корневой элемент правого поддерева
Итак, наша первая операция сборки кучи завершена!
Можно обнаружить, что:После того, как куча построена, наше максимальное значение находится на корневом узле кучи.
Затем замените максимальное значение вершины кучи на последний элемент массива, и мы завершили сортировку.
Далее оставшиеся числа продолжают строить кучи, и перестановка может завершить нашу сортировку кучи.
........создать кучу, поменять местами.... построить кучу, поменять местами... построить кучу, поменять местами... построить кучу, поменять местами..
Три, реализация кода сортировки кучи
Сравните, больше ли текущий родительский узел, чем дочерний узел, и если он больше, замените его, пока не будет завершена сборка одной кучи.~
/**
* 建堆
*
* @param arrays 看作是完全二叉树
* @param currentRootNode 当前父节点位置
* @param size 节点总数
*/
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子树和右字数的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把当前父节点位置看成是最大的
int max = currentRootNode;
if (left < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[right]) {
max = right;
}
}
//如果最大的不是根元素位置，那么就交换
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//继续比较，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
Стоит отметить, что:Когда мы сталкиваемся с сортировкой кучи выше, у нас есть как левое, так и правое поддерево.父>子такое состояние.
- Очевидно, что у обычного массива не может быть такого условия (родитель>потомок), поэтому мыКуча часто строится из последнего элемента массива.
/**
* 完成一次建堆，最大值在堆的顶部(根节点)
*/
public static void maxHeapify(int[] arrays, int size) {
// 从数组的尾部开始，直到第一个元素(角标为0)
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
После завершения первой сборки кучи мы обнаружим, что максимальное значение будет в верхней части массива:
Затем создайте кучу непрерывно, а затем замените последний бит массива на текущую вершину кучи (первый бит массива) для сортировки:
for (int i = 0; i < arrays.length; i++) {
//每次建堆就可以排除一个元素了
maxHeapify(arrays, arrays.length - i);
//交换
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
}
4. Резюме
Кучевая сортировка немного сложнее, чем другие сортировки: она использует для сортировки функцию полного бинарного дерева, а реализация кода немного сложнее, чем у других сортировок.
Использованная литература:
Если в статье есть ошибки, пожалуйста, исправьте меня и поделитесь друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y