Кучи — одна из самых удобных структур данных.
Это упрощает операции по поднятию тяжестей до линейного времени за кулисами без путаницы ссылок.
Удивительно, но сам акт с этим приятелем также довольно легко понять.
Начнем с полезных деталей.
Кучи — это полные бинарные деревья. Если есть 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).