Структура данных кучи: что такое куча? Минимальная и максимальная куча (пример)

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

Куча — это специализированная древовидная структура данных. Куча содержит самый верхний узел, называемый корнем (родительским). Его второй дочерний элемент является левым дочерним элементом корня, а третий узел — правым дочерним элементом корня. Последовательные узлы заполняются слева направо. Ключ родительского узла compares к его потомству, и происходит правильное расположение. Дерево легко визуализировать, где каждый объект называется узлом. Узел имеет уникальные ключи для идентификации.

Зачем вам нужна структура данных кучи?

Вот основные причины использования структуры данных кучи:

  • Структура данных кучи допускает удаление и вставку за логарифмическое время – O(log2п).
  • Данные в дереве формируются в определенном порядке. Помимо обновления или запроса таких параметров, как максимум или минимум, программист может найти связи между родителем и потомком.
  • Вы можете применить концепцию Объектная модель документа чтобы помочь вам понять структуру данных кучи.

Типы куч

Структура данных кучи имеет различные алгоритмы для обработки вставок и удаления элементов в структуре данных кучи, включая Priority-Queue, Binary-Heap, Binomial Heap и Сортировка кучей.

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

Обычно структура данных кучи использует две стратегии. Для входа 12 – 8 – 4 – 2 и 1

  • Min Heap – наименьшее значение вверху
  • Max Heap – наибольшее значение вверху

Типы куч

Мин. Куча

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

Если у вас есть куча Min на дереве, все листья станут жизнеспособными кандидатами. Однако вам необходимо изучить каждый из листьев, чтобы получить точное значение Max-кучи.

Пример минимальной кучи

Пример минимальной кучи

На диаграммах выше вы можете заметить некоторую четкую последовательность от корня до самого нижнего узла.

Предположим, вы храните элементы в массиве Array_N[12,2,8,1,4]. Как видно из массива, корневой элемент нарушает минимальный приоритет кучи. Чтобы сохранить свойство минимальной кучи, вам необходимо выполнить операции min-heapify для замены элементов до тех пор, пока не будут соблюдены свойства минимальной кучи.

Макс. Куча

В структуре Max Heap родительский или корневой узел имеет значение, равное или большее, чем его дочерние элементы в узле. Этот узел содержит максимальное значение. Более того, это полное двоичное дерево, поэтому вы можете построить максимальную кучу из набора значений и запустить ее за время O(n).

Вот несколько методов реализации максимальной кучи Java.

  • Добавлять (): поместить новый элемент в кучу. Если вы используете массив, объекты добавляются в конец массива, а в двоичном дереве объекты добавляются сверху вниз, а затем слева направо.
  • Удалять (): этот метод позволяет удалить первый элемент из списка массива. Поскольку вновь добавленный элемент больше не является самым большим, метод Sift-Down всегда перемещает его на новое место.
  • Просеять вниз (): Этот метод компares корневой объект своему дочернему элементу, а затем помещает вновь добавленный узел на его законное место.
  • Просеять вверх (): если вы используете метод массива для добавления нового вставленного элемента в массив, то метод Sift-Up помогает вновь добавленному узлу переместиться в новое положение. Вновь вставленный элемент сначала сравнивается с родительским путем моделирования древовидной структуры данных.

    Примените формулу Parent_Index=Child_Index/2. Вы продолжаете делать это до тех пор, пока максимальный элемент не окажется в начале массива.

Основные операции с кучей

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

  • Найдите – Найдите предмет в куче.
  • Вставить – Добавить нового дочернего элемента в кучу.
  • Удалить – Удалить узел из кучи.

Создать кучи

Процесс создания куч известен как создание куч. Имея список ключей, программист создает пустую кучу, а затем по одному вставляет другие ключи, используя базовые операции с кучей.

Итак, давайте начнем строить Min-кучу, используя метод Уильяма, вставляя в кучу значения 12,2,8,1 и 4. Вы можете построить кучу из n элементов, начав с пустой кучи, а затем последовательно заполняя ее другими элементами за время O (nlogn).

Создать кучи

  • Heapify: алгоритм вставки, который помогает вставлять элементы в кучу. Проверяется, выделена ли структура данных кучи свойств.

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

  • Слияние. Учитывая, что вам нужно объединить две кучи в одну, используйте кучи слияния, чтобы объединить значения из двух куч. Однако первоначальные кучи до сих пор сохранились.

Осмотреть кучи

Проверка кучи означает проверку количества элементов в структуре данных кучи и проверку того, пуста ли куча.

Важно проверять кучи как сортировку или постановку элементов в очередь. Важно проверить, есть ли у вас элементы для обработки с помощью Is-Empty(). Размер кучи поможет определить максимальную или минимальную кучу. Итак, вам нужно знать следующие элементы:wing свойство кучи.

  • Размер – возвращает величину или длину кучи. Вы можете определить, сколько элементов находится в отсортированном порядке.
  • Пусто – если куча имеет значение NULL, возвращается TRUE, в противном случае возвращается FALSE.

Здесь вы печатаете все элементы в приоритетQ цикл, а затем проверяем, что PriorityQ не пуст.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Использование структуры данных кучи

Структура данных кучи полезна во многих приложениях программирования в реальной жизни, например:

  • Помогает в фильтрации спама.
  • Реализация графовых алгоритмов.
  • Балансировка нагрузки операционной системы и сжатие данных.
  • Найдите заказ в статистике.
  • Внедрите приоритетные очереди, в которых вы можете искать элементы в списке за логарифмическое время.
  • Структура данных кучи также используется для сортировки.
  • Имитация клиентов на линии.
  • Обработка прерываний в Operating System.
  • В кодировании Хаффмана для сжатия данных.

Свойства очереди с приоритетом кучи

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

Шаги по реализации очереди приоритетов кучи в Java

Шаги по реализации очереди приоритетов кучи

Сортировка кучи в JAVA с примером кода

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Результат

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Сортировка кучи в Python с примером кода

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Результат

[1, 3, 4, 7, 9]

Далее вы узнаете о Метод деления пополам

Итоги

  • Куча — это специализированная древовидная структура данных. Представим себе генеалогическое древо с родителями и детьми.
  • Структура данных кучи в Java позволяет удалять и вставлять за логарифмическое время – O(log2п).
  • Кучи в Питон имеет различные алгоритмы для обработки вставок и удаления элементов в структуре данных кучи, включая Priority-Queue, Binary-Heap, Binomial Heap и Heapsort.
  • В структуре Min Heap корневой узел имеет значение, равное или меньшее, чем дочерние узлы этого узла.
  • В структуре Max Heap корневой узел (родительский) имеет значение, равное или большее, чем его дочерние узлы в узле.
  • Проверка кучи означает проверку количества элементов в структуре данных кучи и проверку того, пуста ли куча.