Кучи — одна из самых удобных структур данных.

Это упрощает операции по поднятию тяжестей до линейного времени за кулисами без путаницы ссылок.

Удивительно, но сам акт с этим приятелем также довольно легко понять.

Начнем с полезных деталей.

Кучи — это полные бинарные деревья. Если есть N узлов, N/2 являются родительскими узлами, а остальные являются дочерними/конечными узлами. Кучи можно легко реализовать с помощью массива с корнем в k-м индексе, левым дочерним элементом в позиции 2*k+1 и правым дочерним элементом в позиции 2*k+2.

Два популярных типа кучи:

  • Минимальная куча
  • Макс куча

В Min Heap каждый элемент в каждом корневом/родительском узле меньше или равен своим дочерним узлам. Просто сделайте его противоположным для Max Heap, т.е. каждый элемент в каждом корневом/родительском узле больше или равен его дочерним узлам.

Теперь, почти во всех популярных языках программирования, вы можете легко найти структуру данных, чтобы позаботиться о методах heapify, и вам не нужно заниматься реальной реализацией кучи с нуля, но это полезная информация.

Всякий раз, когда вы добавляете элемент в кучу, на каждом шаге вызывается метод heapify(min или max), который помещает новый элемент в правильное положение.

Каждый элемент в родительском узле сверяется с левым дочерним и правым, и самый большой (самый маленький в случае минимальной кучи) среди них является кандидатом на замену и помещение в родительскую позицию. Та же операция выполняется для всех родительских узлов (index≤N/2)

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

Обсуждение любой структуры данных будет неполным без упоминания ее сложности во время выполнения. С N узлами в дереве:

  • Добавить операции — O(logN)
  • Операция удаления занимает — O(logN)

Логарифмический, так как после добавления или удаления мы вызываем heapify для поддержания порядка. На каждой итерации мы обрабатываем 3 элемента (родительский, левый и правый дочерние элементы) и продвигаемся вперед, пропуская другую половину.

  • Получить максимальный или минимальный элемент — O(1)
  • Построить кучу — O(N)

В Java вы можете использовать приоритетную очередь как кучу. Вам необходимо импортировать пакет java.util.*.

PriorityQueue‹Integer› minHeap = new PriorityQueue‹›();

PriorityQueue‹Integer› maxHeap = new PriorityQueue‹›(Comparator.reverseOrder());

Вы можете использовать концепцию кучи в таких задачах, как получение K самых больших элементов из массива. Наивный подход состоял бы в том, чтобы отсортировать массив и вернуть последние K элементов.

Этот подход займет время O (NlogN), так как вы сортируете массив.

С кучей вы можете сократить время и повысить производительность.

Сначала создайте кучу, а затем удалите элементы, пока счетчик не достигнет K. Таким образом, это займет время O (N + KlogN).