Базовое хранение кучи
Понятие и введение
Куча — это общий термин для особого класса структур данных в информатике.
Куча обычно представляет собой объект-массив, который можно рассматривать как полное двоичное дерево.
Куча удовлетворяет следующим свойствам:
- Значение узла в куче всегда не больше или не меньше значения его родительского узла.
- Куча всегда является полным двоичным деревом.
II. Примечания по применимости
Куча использует структуру полного двоичного дерева для поддержания набора данных, а затем выполняет связанные операции. Временная сложность типичной операции составляетO(1)~O(logn)При этом кучи обычно используются для динамического выделения и освобождения объектов, используемых программами.
Для сценария использования очереди с приоритетом, с обычным массивом или упорядоченным массивом, наихудший случай —O(n^2)структура данных кучи также может повысить эффективность операций постановки в очередь и извлечения из очереди.
| Добавление в очередь | Извлечь из очереди | |
|---|---|---|
| Обычный массив | O(1) | O(n) |
| Упорядоченный массив | O(n) | O(1) |
| Куча | O(logn) | O(log) |
III. Схема структуры
Двоичная куча — это полное двоичное дерево, и значение узла в куче всегда не больше значения его родительского узла. Глубина полного двоичного дерева равна k. За исключением k-го уровня, количество узлов на всех остальных уровнях (от 1 до k-1) достигает максимума, и все узлы на k-м уровне непрерывно сосредоточены на левой стороне.
Куча, корневой узел которой является наибольшим, называется максимальной кучей, как показано на рисунке ниже:

Мы можем использовать массив для хранения двоичной кучи; метки справа — это индексы массива.


Предполагая, что позиция индекса текущего элемента равна i, мы можем вывести правило:
parent(i) = i/2(取整) left child(i) = 2*i right child(i) = 2*i +1
IV. Пример кода на Java
Загрузка пакета исходного кода:Скачать
Код файла src/example/heap/MaxHeap.java:
/**
* Определение кучи
*/
public class MaxHeap<T> {
private T[] data;
private int count;
// Конструктор, создаёт пустую кучу, которая может вместить capacity элементов
public MaxHeap(int capacity){
data = (T[])new Object[capacity+1];
count = 0;
}
// Вернуть количество элементов в куче
public int size(){
return count;
}
// Вернуть boolean, указывающий, пуста ли куча
public boolean isEmpty(){
return count == 0;
}
// Тест MaxHeap
public static void main(String[] args) {
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
System.out.println(maxHeap.size());
}
}