Что такое куча?

Куча - это полная структура двоичного дерева, в которой каждый элемент удовлетворяет свойству кучи. В полном двоичном дереве все уровни заполнены, кроме последнего уровня, то есть узлы на всех уровнях, кроме последнего уровня, будут иметь двух дочерних элементов. Последний уровень будет заполнен слева. Здесь каждый узел кучи хранит ключ значения, который определяет относительное положение этого узла внутри кучи.

Визуализация полного двоичного дерева

Есть два типа куч:

Макс-куча

Все элементы в этой куче удовлетворяют свойству, согласно которому ключ родительского узла больше или равен ключам его дочерних узлов, то есть ключ узла ›= ключ его дочерних узлов. Таким образом, двигаясь вверх от любого узла, мы получаем неубывающую последовательность ключей, а, двигаясь вниз от любого узла, мы получаем невозрастающую последовательность ключей. В частности: самый большой ключ в максимальной куче находится в корне.

Мин-куча

Все элементы в этой куче удовлетворяют свойству, согласно которому ключ родительского узла меньше или равен ключам его дочерних узлов, то есть ключ узла ‹= ключ его дочерних узлов. Таким образом, двигаясь вверх от любого узла, мы получаем неубывающую последовательность ключей, а, двигаясь вниз от любого узла, мы получаем неубывающую последовательность ключей. В частности: самый большой ключ в максимальной куче находится в корне.

Особые примечания, относящиеся к куче

  • Двоичная куча - это двоичное дерево, которое удовлетворяет двум свойствам: (1) свойство формы: все уровни, кроме последнего уровня, полностью заполнены, а последний уровень заполняется слева направо (2) свойство кучи
  • Обход кучи в порядке уровней даст порядок, в котором элементы заполняются в массиве.
  • Куча - это полная древовидная структура, поэтому мы определяем высоту узла в куче как количество ребер на самом длинном пути от узла к листу.
  • Мы определяем высоту кучи как высоту ее корня. Поскольку куча из n элементов основана на полном двоичном дереве, ее высота равна O (logn).
  • В худшем случае мы увидим, что основные операции с кучами выполняются во времени, пропорциональном высоте дерева, и, таким образом, занимают время O (logn).

Реализация массива кучи

Двоичная куча может быть представлена ​​с помощью массива, в котором индексы массива фиксируют отношения родитель-потомок. Предположим, что A [] - это массив кучи размера n:

  • Корень двоичной кучи хранится в A [0].
  • Для данного элемента A [i] дочерние элементы этого элемента хранятся в A [2i + 1] и A [2i + 2], если они существуют.
  • Левый дочерний элемент i обозначается как left (i) = A [2i + 1], если 2i + 1 ‹n
  • Правый дочерний элемент i обозначается как right (i) = A [2i + 2], если 2i + 2 ‹n
  • Родитель A [i] хранится в A [(i − 1) / 2].

Примечание. В большинстве языков программирования эти операции можно эффективно реализовать с помощью побитовых операторов. Следовательно, представление массива - это подход с экономией места, поскольку нам не нужно хранить дополнительные 3 указателя на узел в куче.

  • Таким образом, для максимальной кучи мы можем сказать, что A [i] ≥ A [2i + 1] и A [i] ≥ A [2 * i + 2], где (2 * i + 1) и (2i + 2) являются ‹п. Как мы знаем, ключ каждого узла в максимальной куче больше, чем ключ его дочерних узлов, следовательно, максимальный ключ в куче будет храниться в корне, то есть в A [0].
  • Точно так же минимальная куча будет удовлетворять свойству, что для любого индекса i A [i] ≤ A [2i + 1] и A [i] ≤ A [2 * i + 2], где (2 * i + 1) и (2i + 2) - ‹n. Таким образом, для минимальной кучи минимальный элемент будет в корне кучи и, следовательно, в A [0].

Операции, поддерживаемые Max-Heap

Различные операции, поддерживаемые max heap, подробно описаны ниже и будут рассмотрены более подробно в следующих статьях:

  • maxHeapify (A [], i): это метод переупорядочивания элементов кучи для сохранения свойства кучи. Этот процесс требуется, когда определенный узел с индексом i вызывает дисбаланс в куче из-за некоторой операции на этом узле.
  • buildMaxHeap (A []): мы можем использовать процедуру для преобразования входного массива в max-heap.
  • findMax (heap []): эта операция возвращает максимальное значение в куче, а ее временная сложность составляет O (1), поскольку ей просто нужно вернуть A [0].
  • extractMax (A []): эта операция удаляет максимальный элемент из кучи и возвращает его. Временная сложность этой операции составляет O (logn), поскольку мы заменяем A [0] на A [n-1] - последний элемент кучи, а затем выполняем некоторые операции для поддержания свойства max-heap.
  • IncreaseKey (A [], i, v): эта операция увеличивает значение индекса i в массиве до значения v. Эта операция действительна, только если A [i] ≤ v, то есть новое значение больше, чем существующее значение в индексе i. Это гарантирует, что поддерево с корнем в индексе i по-прежнему является максимальной кучей. Сложность этой операции составляет O (logn), поскольку после увеличения ключа с индексом i свойство max-heap Parent (i) может быть нарушено, и нам может потребоваться выполнить некоторые операции для его восстановления.
  • insertKey (A [], v): Эта операция вставляет элемент v в кучу, ее сложность составляет O (logn). Чтобы реализовать эту операцию, мы добавляем элемент в конец кучи (в A [n-1]), а затем выполняем некоторые операции для восстановления свойства кучи.
  • deleteKey (A [], i): эта операция используется для удаления элемента с индексом i, сложность этой операции составляет O (logn). Чтобы удалить любой элемент, мы можем заменить его последним элементом кучи, а затем снова выполнить операции по восстановлению свойства кучи в случае его нарушения.

Аналогичным образом min-heap поддерживает следующие операции:

  • minHeapify (A [], я)
  • buildMinHeap (A [])
  • findMin (A [])
  • extractMin (A [])
  • уменьшениеKey (A [], i, v)
  • insertKey (A [], v)
  • deleteKey (A [], i).

Популярные приложения Heap

  • Кучи используются для эффективной реализации очереди приоритетов, важной структуры данных в информатике. Одно из приложений приоритетных очередей - планирование процессов в операционных системах.
  • Кучи используются алгоритмом Heapsort, который является одним из самых быстрых известных алгоритмов сортировки. Его сложность - O (nlogn).
  • Кучи также используются в эффективных реализациях алгоритмов, таких как алгоритм кратчайшего пути Дейкстры, где нам нужно выбрать узел, ближайший к данному узлу. Если расстояния до всех узлов хранятся в куче, то ближайший узел может быть эффективно извлечен с помощью min-heap.
  • Кучи предоставляют эффективный способ получить k-й наименьший или наибольший элемент в массиве.

Критические идеи думать!

  • Как вычислить дочерние и родительские узлы любого узла с индексом i с помощью побитовых операций?
  • Как мы можем реализовать кучу с помощью указателей?
  • Каковы будут преимущества использования указателей для реализации кучи? В каких случаях мы должны предпочесть реализацию указателя реализации массива?
  • Минимальное количество элементов в куче высотой h - 2 ^ h.
  • Максимальное количество элементов в куче высотой h составляет 2 ^ (h + 1) - 1.
  • Где находится наименьший элемент в максимальной куче, если предположить, что все элементы различны?
  • Является ли отсортированный массив минимальной кучей?
  • В представлении массива для хранения кучи из n элементов листья - это узлы, индексированные n / 2, n / 2 + 1, n / 2 + 2… .. n-1.

Наслаждайтесь обучением, наслаждайтесь алгоритмами!