предисловие
В последнее время очевидно, что частота обновления статей уменьшилась, потому что я дополняю актуальные знания о структурах данных и алгоритмах, что равносильно обучению с нуля.
После поиска большого количества видео и материалов я наконец обнаружил, что видеоуроки Shang Silicon Valley на станции b относительно хороши, всего 195 серий. Каждый раздел объясняется в соответствии с первой концепцией, принципом, а затем этапами реализации кода. Если вы также готовы начать работу со структурами данных и алгоритмами, я рекомендую прочитать эту серию руководств.
Вчера за один день посмотрел более 40 серий, от второй половины дерева до целой части картинки. Как видите, каждая серия на самом деле не такая уж и длинная, всего несколько минут и полчаса. Открой 2x скорость, чтобы смотреть, так лучше.
Без лишних слов, давайте к делу.
Введение в двоичную кучу
Мы знаем, что существует много видов деревьев, наиболее часто используемым является бинарное дерево. Двоичное дерево имеет полное бинарное дерево и полное бинарное дерево. Двоичная куча — это структура данных, основанная на полном двоичном дереве. Он имеет следующие две характеристики.
- Во-первых, это полное бинарное дерево
- Во-вторых, значение любого родительского узла в куче больше или равно (или меньше) его левого и правого дочерних узлов.
Следовательно, согласно второй характеристике, бинарная куча делится на большую верхнюю кучу (или называемую максимальной кучей) и маленькую верхнюю кучу (или называемую минимальной кучей).
Как следует из названия, большая верхняя куча — это куча, родительский узел которой больше или равен левому и правому дочерним узлам, а маленькая верхняя куча — это куча, родительский узел которой меньше левого и правого дочерних узлов.
Взгляните на примерную диаграмму большой верхней кучи, маленькая верхняя куча аналогична, но маленькое значение находится сверху.
Примечание. Куча с большой вершиной гарантирует только то, что родительский узел больше, чем значение левого и правого дочерних узлов, и не обязан гарантировать порядок размеров между левым и правым дочерними узлами. На рисунке левый дочерний узел 6 из 7 больше правого дочернего узла 1, а левый дочерний узел 4 из 8 меньше правого дочернего узла 5. (То же самое для маленькой верхней кучи)
построить двоичную кучу
Мы знаем определение двоичной кучи, а затем даем вам неупорядоченное полное двоичное дерево, как встроить его в двоичную кучу?
В качестве примера возьмем кучу с большой вершиной. Учитывая следующий массив (полные двоичные деревья обычно хранятся в массивах)
{4, 1, 9, 3, 7, 8, 5, 6, 2}Рисуем его начальное состояние, а потом разбираем, как шаг за шагом построить большую верхнюю кучу.
Из-за большой верхней кучи значение родительского узла больше, чем у левого и правого дочерних узлов, поэтому корневой узел дерева должен иметь наибольшее значение среди всех узлов. Поэтому нам нужно начать с последнего уровня дерева и постепенно корректировать большое значение вверх (обменять местами больший узел левого и правого дочерних узлов с родительским узлом) до первого уровня.
На самом деле, если быть более конкретным, его следует настраивать из следующих нелистовых узлов. Подумайте, почему.
Подумайте об этом в обратном порядке, если вы начинаете с первого слоя, например, после того, как 4 и 9 поменялись местами на картинке, вы не можете гарантировать, что 9 будет максимальным значением всех узлов (ну, пример на картинке может не очень хорошо, это ровно 9 максимум). Если внизу есть числа выше 9, вам в конечном итоге потребуется пройти настройку снизу вверх. Ну, я мог бы также просто начать настройку снизу вверх.
Кроме того, зачем начинать с самого нижнего нелистового узла (узел 3 на графике). Поскольку ниже листового узла нет дочернего узла, его можно сравнивать только с родительским узлом, начиная с листового узла бессмысленно.
На первом шаге начните с 3 в качестве родительского узла, сравните их дочерние узлы 6 с 2, 6 является самым большим, а затем поменяйте позиции с 3.
На втором шаге сравниваются 6 и 7, 7 является самой большой, а 7 и 1 меняются позициями.
На третьем шаге сравниваются 7 и 9, 9 является самой большой, а 9 и 4 меняются позициями.
На четвертом шаге мы обнаружили, что после позиции обмена есть более крупная позиция ниже 4, поэтому нам нужно использовать 4 в качестве родительского узла и его левого и правого дочерних узлов для сравнения. 8 оказывается самым большим, тогда 8 и 4 меняются местами.
Наконец, достигается построение большой верхней кучи. Следующий код реализует процесс обмена.
/**
* 调整为大顶堆
* @param arr 待调整的数组
* @param parent 当前父节点的下标
* @param length 需要对多少个元素进行调整
*/
private static void adjustHeap(int[] arr, int parent, int length){
//临时保存父节点
int temp = arr[parent];
//左子节点的下标
int child = 2 * parent + 1;
//如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
while(child < length){
//判断左子节点和右子节点的大小,若右边大，则把child定位到右边
if(child + 1 < length && arr[child] < arr[child + 1]){
child ++;
}
//若child大于父节点，则交换位置，否则退出循环
if(arr[child] > temp){
//父子节点交换位置
arr[parent] = arr[child];
//因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
//把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
parent = child;
child = 2 * parent + 1;
}else{
//如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
//因此无需继续循环
break;
}
}
//把当前节点值替换为最开始暂存的父节点值
arr[parent] = temp;
}
public static void main(String[] args) {
int[] arr = {4,1,9,3,7,8,5,6,2};
//构建一个大顶堆，从最下面的非叶子节点开始向上遍历
for (int i = arr.length/2 - 1 ; i >= 0; i--) {
adjustHeap(arr,i,arr.length);
}
System.out.println(Arrays.toString(arr));
}
//打印结果： [9, 7, 8, 6, 1, 4, 5, 3, 2]。 和我们分析的结果一模一样В цикле while логика if(arr[child] > temp) else соответствует третьему и четвертому шагам на рисунке. То есть нужно следить, чтобы обмениваемый дочерний узел был больше дочернего узла под ним, иначе нужно продолжить цикл и скорректировать положение.
сортировка кучей
Сортировка кучей заключается в использовании для сортировки характеристик большой кучи или маленькой кучи.
Его основная идея заключается в следующем:
- Построить текущий массив в кучу с большим верхом.
- В этот момент корневой узел должен иметь наибольшее значение среди всех узлов, и если он поменяется местами с последним элементом, последний элемент будет иметь наибольшее значение.
- Перестроение оставшихся n - 1 элементов в кучу с большой вершиной дает максимум из n - 1 элементов. Повторение этого действия приведет все элементы в порядок.
шаг:
Возьмите приведенный выше массив в качестве примера и посмотрите на процесс сортировки кучи.
Всего есть девять элементов, настройте их на большую верхнюю кучу, а затем поменяйте местами верхний элемент 9 и нижний элемент 2.
На данный момент 9 уже в порядке и не нуждается в корректировке. Затем соберите оставшиеся восемь элементов в большую верхнюю кучу, а затем поменяйте местами верхние и последние элементы восьми элементов, как показано ниже, 8 и 3 меняются местами.
На данный момент 8 и 9 уже в порядке и не нуждаются в корректировке. Затем подгоните оставшиеся семь элементов к большой верхней куче, а затем поменяйте местами верхний и последний элементы кучи из этих семи элементов. Ниже 7 и 2 меняются местами.
И так далее, после n - 1 корректировок цикла, когда в конце остался только один элемент, сравнивать не нужно, т.к. это уже минимальное значение.
Это может показаться сложным процессом, но на самом деле он очень эффективен. Нет добавления или удаления, просто напрямую измените исходный массив. Поскольку мы знаем, что добавление и удаление массива происходит относительно медленно, каждый раз, когда элемент удаляется или вставляется, необходимо перемещать n элементов позади массива. Кроме того, он не занимает лишнего места.
Код:
//堆排序，大顶堆，升序
private static void heapSort(int[] arr){
//构建一个大顶堆，从最下面的非叶子节点开始向上遍历
for (int i = arr.length/2 - 1 ; i >= 0; i--) {
adjustHeap(arr,i,arr.length);
}
System.out.println(Arrays.toString(arr));
//循环执行以下操作：1.交换堆顶元素和末尾元素 2.重新调整为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
//将堆顶最大的元素与末尾元素互换，则数组中最后的元素变为最大值
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//从堆顶开始重新调整结构，使之成为大顶堆
// i代表当前数组需要调整的元素个数，是逐渐递减的
adjustHeap(arr,0,i);
}
}Временная сложность и пространственная сложность:
Сортировка кучи, временная сложность каждой корректировки большой верхней кучи составляет O(logn), а n элементов необходимо циклически корректировать всего n-1 раз, поэтому временная сложность сортировки кучи составляет O(nlogn). Его математический вывод более сложен, и заинтересованные студенты могут самостоятельно проверить соответствующую информацию.
Поскольку дополнительное пространство памяти не занято, объемная сложность сортировки кучей составляет O (1).