Сортировка кучей - Сортировка кучей
Сортировка кучей относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Куча — это структура, которая аппроксимирует полное бинарное дерево и в то же время удовлетворяет свойству укладки в стопку: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла.
характеристики кучи
- Структура данных кучи аналогична полному бинарному дереву, то есть каждый узел имеет два дочерних узла.
- Когда значение узла меньше или равно значению родительского узла и больше или равно значению дочернего узла, называется большой верхней кучей (то есть значение корневого узла является наибольшим). )
- Когда значение узла больше или равно значению родительского узла и меньше или равно значению дочернего узла, это называется малой верхней кучей (то есть значение корневого узла равно наименьший)
- Если индекс текущего узла равен k, то индекс левого дочернего узла равен 2.k + 1, индекс правого дочернего узла равен 2k + 2, индекс родительского узла равен (k - 1)/2
В этой статье в качестве примера мы возьмем большую верхнюю кучу.
Действия с кучей — с плавающей запятой
Плавающая: при построении кучи, если значение узла больше родительского узла, текущий узел и родительский узел меняются местами; пока узел меньше родительского узла, плавание прекращается (это можно понимать как новый сотрудник с выдающимися способностями и более высокой позицией); эффект следующий
код показывает, как показано ниже:
private void siftUp(int k) {
// k == 0 时表明上浮到根节点，结束上浮操作
while (k > 0) {
// 获取父节点索引
int parent = (k - 1) / 2;
// 小于父节点时退出，结束上浮操作
if (less(parent, k)) {
break;
}
// 与父节点交换数据
swap(parent, k);
// 改变 k 的指向 继续上浮
k = parent;
}
}
Действие кучи - сток
Погружение: относится к процессу построения кучи, если значение текущего узла меньше, чем дочерний узел, текущий узел и дочерний узел обмениваются местами до тех пор, пока узел не станет больше, чем дочерний узел, чтобы прекратить погружение (это может быть понял, что лидер выпадает, когда способности посредственные. Процесс задания немного убогий); эффект следующий
код показывает, как показано ниже:
private void siftDown (int k, int length) {
// 获取左子节点索引
int childIndex = 2 * k + 1;
// 判断是否存在子节点
while (childIndex < length) {
// 判断左右子节点 查找最大的子节点
if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) {
childIndex++;
}
// 若当前节点大于子节点 退出循环
if (less(k, childIndex)) {
break;
}
// 判断当前节点是否小于子节点, 若小于执行交换
swap(k, childIndex);
// 改变 k 指向
k = childIndex;
childIndex = 2 * k + 1;
}
}
сортировка кучей
Итак, как использовать структуру данных кучи для сортировки неупорядоченного массива?
- Во-первых, неупорядоченный массив создается в виде максимальной кучи, а корневой узел является максимальным значением в это время.
- Поменяйте местами последний узел со значением корневого узла и удалите максимальный узел;
- Повторно выполните оставшиеся узлы, чтобы построить кучу
- Повторите шаги 2 и 3
Куча построения неупорядоченного массива
Построение кучи из неупорядоченного массива может быть выполнено путем плавания или опускания.
Как показано на рисунке выше, для上浮Способ построения кучи, процесс заключается в выполнении плавающей операции над каждым элементом массива, начиная с нижнего индекса 0, до тех пор, пока, наконец, не будет получена упорядоченная большая верхняя куча.
Как показано на рисунке выше, для下沉Процесс построения кучи заключается в выполнении операции опускания над каждым элементом массива, начиная с нелистового узла по очереди, пока, наконец, не будет получена упорядоченная большая верхняя куча.
код показывает, как показано ниже:
for (int i = 0; i < array.length; i++) {
// 上浮方式构建堆
siftUp(i);
}
// 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点
// 采用下沉的方式 从下往上构建子堆
for (int i = array.length / 2; i >= 0; i--) {
siftDown(i, array.length);
}
После завершения первоначального построения кучи оставшаяся часть работы заключается в повторении следующей логики (в этом месте нет рисунка):
- Поменять местами элементы между хвостовыми и корневыми узлами
- Удалите хвостовой узел и создайте подкучу для оставшихся элементов (способ построения кучи такой же, как и для начальной кучи).
Полный код выглядит следующим образом:
public class HeapSort {
private int[] array;
public HeapSort(int[] array) {
this.array = array;
}
private boolean less (int i, int j) {
return array[i] > array[j];
}
private void swap (int k, int j) {
int temp = array[k];
array[k] = array[j];
array[j] = temp;
}
/**
* 下沉操作
*
* @param k
*/
private void siftDown(int k, int length) {
// loop
// 判断是否存在子节点
int childIndex = 2 * k + 1;
while (childIndex < length) {
// 查找最大的子节点
if (childIndex + 1 < length && !less(childIndex, childIndex + 1)) {
childIndex++;
}
// 若当前节点大于子节点 退出循环
if (less(k, childIndex)) {
break;
}
// 判断当前节点是否小于子节点, 若小于执行交换
swap(k, childIndex);
// 改变 k 指向
k = childIndex;
childIndex = 2 * k + 1;
}
}
/**
* 上浮操作
*
* @param k
*/
private void siftUp(int k) {
while (k > 0) {
int parent = (k - 1) / 2;
// 小于父节点时退出
if (less(parent, k)) {
break;
}
// 与父节点交换数据
swap(parent, k);
// 改变 k 的指向
k = parent;
}
}
public void sort () {
// 构造堆
for (int i = 0; i < array.length; i++) {
siftUp(i);
}
print();
int n = array.length - 1;
while (n > 0) {
// 因为每次完成堆的构造后, 根节点为最大(小)值节点
// 将根节点与最后一个节点交换
swap(0, n);
for (int i = 0; i <= n - 1; i++) {
// 排除有序的节点
// 重新构造堆
siftUp(i);
}
print();
n--;
}
}
private void sort1 () {
// 构建堆
// 因为堆是完全二叉树的特性, 所以下标小于等于 array.length / 2 的节点为非叶子节点
// 采用下沉的方式 从下往上构建子堆
for (int i = array.length / 2; i >= 0; i--) {
siftDown(i, array.length);
}
print();
int n = array.length - 1;
while (n > 0) {
// 因为每次完成堆的构造后, 根节点为最大(小)值节点
// 将根节点与最后一个节点交换
swap(0, n);
for (int i = n / 2; i >= 0; i--) {
// 排除有序的节点
// 重新构造堆
siftDown(i, n);
}
print();
n--;
}
}
private void print () {
for (Integer num : array) {
System.out.print(num);
System.out.print(",");
}
System.out.println("");
}
public static void main(String[] args) {
int[] array = {10, 40, 38, 20, 9, 15, 25, 30, 32};
new HeapSort(array).sort();
System.out.println("");
new HeapSort(array).sort1();
}
}
Резюме: Где применяется сортировка кучей? Вы можете обратиться к реализации приоритетной очереди PriorityQueue