Что такое куча?
Куча — это особый вид дерева, если выполняются следующие два условия, это куча:
(1) куча — это полное бинарное дерево;
(2) Значение узла в куче всегда не больше (или не меньше) значения его родительского узла.
Среди них мы называем кучу с самым большим корневым узлом большой верхней кучей, а кучу с наименьшим корневым узлом маленькой верхней кучей.
Сведения о куче
полное бинарное дерево
Полное бинарное дерево относится к бинарному дереву, в котором все уровни достигают максимального количества узлов. Например, следующее дерево:
полное бинарное дерево
Полное бинарное дерево означает, что все слои, кроме последнего слоя, достигают максимального количества узлов, а узлы последнего слоя располагаются слева. Например, следующее дерево:
Видно, что, по сути, полное бинарное дерево — это особый вид полного бинарного дерева.
Итак, какую структуру наиболее эффективно использовать для хранения полного бинарного дерева?
Мы можем видеть, что полные узлы двоичных деревьев являются относительно компактными, и только последний недовольный, поэтому используйте массив самой космической экономии, например, приведенный выше Fengyun Complete Binary Tree, мы можем хранить.
Мы не храним элементы в позиции с индексом 0, а сохраняем элементы из позиции с индексом 1. Каждый слой хранится в массиве слева направо.
Почему нет элемента в позиции нижнего индекса 0?
Это потому, что мы можем легко найти родительский узел, сохранив его таким образом.Например, родительский узел 4 равен 4/2=2, а родительский узел 5 равен 5/2=2.
куча
Куча также является полным бинарным деревом, но его элементы должны удовлетворять условию, что значение каждого узла не больше (или меньше) значения его родительского узла. Например, следующая куча:
Ранее мы говорили, что полное бинарное дерево подходит для использования массивов для хранения, так как же следует хранить указанную выше кучу?
Точно так же мы в индексной позиции 0 не существует элемента, наконец, становится таким ниже.
В это время, если мы хотим найти родительский узел 8, мы возьмем нижний индекс позиции 5/2=2 из 8, который является позицией узла 5, который мы также собираем позже.
вставить элемент
После вставки элемента в кучу нам нужно продолжать удовлетворять два свойства кучи, а именно:
(1) куча — это полное бинарное дерево;
(2) Значение узла в куче всегда не больше (или не меньше) значения его родительского узла.
Чтобы выполнить условие (1), мы вставляем элемент на одну позицию после последнего узла последнего слоя, но условие (2) может уже не выполняться после вставки, поэтому в это время нам нужно куча.
Например, выше кучи нам нужно вставить элементы 2, мы помещаем его в спину 9, когда условие (2), и нам нужна куча. (Это маленькая топ-куча)
Полное бинарное дерево и массив рассматриваются.
В полном бинарном дереве вставленный узел сравнивается со своим родительским узлом, если он меньше родительского узла, то меняются их местами, а затем сравниваются с родительским узлом, если он меньше родительского узла, то меняются местами пока он не станет меньше родительского узла, пока узел не станет большим.
В массиве, если вставленный узел меньше узла в позиции n/2, если он меньше узла в позиции n/2, его позиции меняются местами, а затем сравниваются с узлом в позиции n/4, если он меньше, чем узел в позиции n/4. Узел в позиции 4 меньше, а затем меняют местами, пока он не станет больше, чем узел в позиции n/(2^x).
Вот что происходит, когда элемент вставляетсякуча, также называемое нагромождением снизу вверх.
Процесс вставки элементов мы знаем, что каждая позиция сравнивается с n/(2^x), следовательно, временная сложность вставки элемента равна O(log n).
Удалить верхнюю часть элемента кучи
Мы знаем, что самый маленький элемент хранится в верхней части кучи в маленькой верхней куче, что, если мы его удалим?
После удаления верхнего элемента кучи, чтобы две характеристики кучи по-прежнему удовлетворялись, сначала мы можем переместить последний элемент на позицию корневого узла, тогда выполняется условие (1), а затем условие ( 2) устраивает., его нужно наворочить.
Сравните полное бинарное дерево с массивом.
В полном бинарном дереве поместите последний узел на вершину кучи, а затем поменяйте позицию с меньшими левым и правым дочерними узлами (потому что это маленькая верхняя куча) и спускайтесь по очереди, пока он не станет меньше, чем левый и правый дочерние узлы.
В массиве переместите последний элемент на позицию с индексом 1, а затем сравните его с позициями с индексом 2 и 3. Найдено, что 8 больше 2, а 2 — наименьшее между 2 и 3, поэтому поменяйте позиции с 2 ; Затем сравните позиции с нижними индексами 4 и 5 и найдите, что 8 больше, чем 5, а 5 наименьшее из 5 и 7, поэтому он поменяется местами с 5, нет левого и правого потомков узлов, и нагромождение заканчивается.
Это делается при удалении элементовкуча, также называемое нагромождением сверху вниз.
Из процесса удаления элементов мы знаем, что после того, как последний элемент переносится в корневой узел, каждый раз он сравнивается с элементами на 2n и (2n+1) позициях, в зависимости от того, что меньше, поэтому временная сложность удаления элементов также O (log n).
строить кучу
Учитывая набор неупорядоченных массивов, как нам построить кучу?
Как показано на рисунке ниже, мы имитируем последовательное добавление элементов в кучу.
(1) Элемент 6 вставляется только в один, без сравнения;
(2) Вставьте элемент 8, который больше 6 и не требует замены;
(3) Вставьте элемент 3, который меньше элемента 6, в позицию нижнего индекса 3/2=1 и поменяйте позицию;
(4) Вставить элемент 2, который меньше элемента 8 в позиции нижнего индекса 4/2=2, поменять позицию, и меньше элемента 3 в позиции нижнего индекса 2/2=1, поменять позицию;
(5)...
(10) Наконец, все вставки завершены, то есть процесс построения кучи завершен.
Мы знаем, что высота полного бинарного дерева равна h=log n, а h-й уровень имеет 1 элемент, (h-1)-й уровень имеет 2 элемента, (h-2)-й уровень имеет 2^2 элемента, ... , первый уровень имеет 2^(h-1) элементов.
На самом деле количество сравнений узла во всем процессе построения пропорционально его высоте K, например 1 на приведенном выше рисунке, также он сравнивает 3 раза с последнего слоя (высота H = 4) Только текущее положение приехал.
Следовательно, можно сделать вывод, что в h-м слое имеется 1 элемент, который нужно сравнить не более (h-1) раз, в (h-1)-м слое 2 элемента, которые сравниваются не более ( h-2) раз; h-2) уровень содержит 2^2 элемента, и они сравниваются не более (h-3) раз; ...; уровень 1 содержит 2^(h-1) элементов, и они сравниваются не более 0 раз.
Следовательно, сумма следующая:
Следовательно, временная сложность построения кучи составляет O(n).
сортировка кучей
Мы знаем, что для небольшой верхней кучи элементы, хранящиеся в верхней части кучи, являются наименьшими.
Затем мы удаляем верхний элемент кучи, помещаем его в кучу, второй наименьший идет на вершину кучи, снова удаляем его и снова собираем... Эти удаленные элементы просто по порядку?
Конечно, процесс сортировки стека очень прост.
Мы напрямую меняем позицию элемента в верхней части кучи на n-й элемент, затем кучаем первые (n-1) элементы, а затем меняем позицию верхнего элемента на (n-1)-й элемент, и затем помещаем первые (n-1) элементы в кучу.-2) Элементы складываются в кучу, .. и т. д. Наконец, элементы в массиве меняются местами, и сортировка завершается.
Мы знаем, что временная сложность удаления одного элемента равна O(log n), тогда удаление n элементов равно:
log n + log(n-1) + log(n-2) + log 1
Эта формула приблизительно равна nlog n, поэтому временная сложность сортировки в куче равна O(nlog n).
Более того, эта сортировка не требует дополнительного места, требуется только временная переменная для обмена элементами, поэтому сложность памяти при сортировке кучи составляет O(1).
Суммировать
(1) куча — это полное бинарное дерево;
(2) Каждый узел в малой (большой) верхней куче не меньше (не больше) своего родительского узла;
(3) Временная сложность вставки и удаления элементов из кучи составляет O(log n);
(4) Временная сложность построения кучи составляет O(n);
(5) Временная сложность сортировки кучи составляет O(nlog n);
(6) Объемная сложность сортировки кучи равна O(1);
пасхальные яйца
Какое его приложение имеет это?
На самом деле, помимо сортировки кучи, кучи можно использовать и во многих других целях, таких как нахождение медианы, 99% цифр и задачи синхронизации.
Например, общая идея нахождения медианы состоит в том, чтобы построить большую верхнюю кучу и маленькую верхнюю кучу соответственно, а затем поместить элементы в эти две кучи.Когда количество элементов в одной куче на 2 больше, чем в другой, это будет сбалансировано.Один (или два) из элементов в верхней части двух стеков является медианой после размещения всех элементов.
Добро пожаловать, чтобы обратить внимание на мою общедоступную учетную запись «Брат Тонг читает исходный код», проверить больше статей из серии исходного кода и поплавать в океане исходного кода с братом Тонгом.
