Пример работы кучи в Golang
Давай попробуем создать кучу Max с помощью GoLang и запустить ее. Ниже рассмотрим исходный код с последовательным объяснением методов.
Пришло время поработать с кодом!
- Во-первых, мы создаем структуру Max Heap. В этой структуре у нас есть срез с именем array.
Нам нужно несколько вспомогательных функций, таких как:
-
right — вернуть правого потомка родителя;
-
left — вернуть левого потомка родителя;
-
parent — вернуть родителя;
-
swap — поменять местами элементы.
Мы используем представленные выше математические функции, чтобы получить левого и правого потомка от родителя.
-
В методе Insert мы попытаемся вставить новый ключ Max Heap. Итак, добавим новое значение в массив (append добавит ключ в конец массива).
-
Далее нам нужно выполнить процесс maxHeapifyUp, чтобы сохранить структуру данных кучи. Затем maxHeapifyUp проверит свое значение: если оно больше значения его родителя, maxHeapifyUp поменяется местами с родительским узлом и снова проверит, будет ли его значение больше, чем его новый родительский узел. Этот процесс будет происходить до тех пор, пока h.array[parent(index)] < h.array[index] , то есть пока значение maxHeapifyUp будет не больше значения его родительского узла.
-
В методе Extract мы возвращаем родительский узел, который является первым элементом массива., А затем устанавливаем последний элемент массива в первый элемент и удаляем из массива последний элемент, который не установлен как корневой (потому что нам не нужны дубликаты).
-
Затем нам нужно выполнить процесс maxHeapifyDown, чтобы сохранить структуру данных кучи. В процессе maxHeapifyDown мы получаем левый и правый дочерние элементы корня, получаем максимальное значение и меняем местами эти значения до тех пор, пока h.array[index] < h.array[childToCompare], то есть пока не получим максимальное значение childtoCompare из левого и правого дочерних элементов.
С оригиналами статей, которые использовались для подготовки данной темы, ты можешь ознакомиться ниже: