Свойства кучи
Куча - это полностью двоичное дерево, которое может быть реализовано в реальности с помощью массива. Одним из наиболее важных свойств является то, что любой узел меньше (больше, чем), равняется его дочерним узлам. Куча с наименьшим корневым узлом называется наименьшей кучей, а куча с самым большим корневым узлом называется самой большой кучей. На следующем рисунке показан пример наибольшей кучи и ее массива, который можно интуитивно видно, что каждый узел больше, чем его дети.
Как видно на рисунке выше, узлы полностью двоичного дерева могут быть расположены по порядку из корневого узла № 1, соответствующие индексу в массиве A (обратите внимание, что индекс здесь начинается с 1). Учитывая узел I, мы можем легко получить его левого ребенка 2i, правый ребенок - 2i+1, а родительский узел - i/2
Основные операции кучи
Есть две основные операции для кучи (см. Минимальную кучу в качестве примера ниже):
Вставьте элемент K: добавьте K непосредственно к концу массива, а затем пузырьте, чтобы отрегулировать кучу. Операция пузырьков: сравните элемент, который будет скорректирован с его родительским узлом, и если он больше, чем его родительский узел, обменяйте его до тех пор, пока свойства кучи не будут восстановлены.
Извлеките наибольшее значение: наибольшее значение является корневым элементом. Затем удалите его, пусть корневой элемент = последний элемент узла листового узла, а затем пузырьте из корневого элемента, чтобы регулировать кучу. Операция пузырьков: каждый раз вы должны выбирать наименьший детский узел из трех узлов, чтобы регулировать узел, у которого левые и правые дети обмениваются (если наименьшее, ему не нужно обменять), пока свойства кучи не будут восстановлены.
На практике часто необходимо построить неупорядоченный массив, содержащий n элементов в кучи. Конструктор в классе Heap ниже будет показывать, как построить кучу через регулировку пузырька _bubbledown. Куча, по сути, является полностью двоичным деревом, а высота дерева всегда логика. Отражающая много времени работы каждой основной операции заключается в том, чтобы пузыриться и приспосабливаться к свойствам кучи, поэтому их сложность времени-O (nlogn) o (nlogn).
Пример Java:
// Float Public void Swim (int k) {while (k/2> = 1 && mess (pq [k/2], pq [k])) {Exch (pq, k/2, k); k = k/2; }} // Snined Private void sink () {int k = 1; while (2*k <n) {int j = 2*k; if (меньше (pq [j], pq [j+1])) j ++; if (меньше (pq [k], pq [j])) Exch (pq, k, j); еще разрыв; k = j; }} Принцип реализации сортировки кучи
Он разделен на два шага:
1. Организации массивов в приказе двоичной кучи
2. Измените положение корневого узла и последний узел, а затем погрузите корневой узел.
выполнить:
Возможно, мой код немного отличается от приведенной выше анимации, но основные принципы похожи.
Общедоступный класс Heapsort расширяет basesort {private int n; @Override public void sort (сопоставимо [] a) {n = a.length-1; int k = n/2; while (k> = 1) {раковина (a, k); k--; } k = 1; while (k <= n) {Exch (a, k, n--); раковина (a, k); }}}