Базовое хранение кучи

Понятие и введение

Куча — это общий термин для особого класса структур данных в информатике.

Куча обычно представляет собой объект-массив, который можно рассматривать как полное двоичное дерево.

Куча удовлетворяет следующим свойствам:

  • Значение узла в куче всегда не больше или не меньше значения его родительского узла.
  • Куча всегда является полным двоичным деревом.

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:

package example.heap;

/**
* Определение кучи
 */

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());
    }
}
Другие расширения