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

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

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

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

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

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

Типы куч

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

Приоритетная очередь: Это абстрактная структура данных, содержащая приоритетные объекты. Для каждого объекта или элемента заранее установлен приоритет. Таким образом, объект или элемент, которому присвоен более высокий приоритет, получает услугу раньше остальных.
Двоичная куча: Двоичные кучи подходят для простых операций с кучами, таких как удаление и вставка.
Биномиальная куча: Биномиальная куча состоит из серии наборов биномиальных деревьев, составляющих кучу. Биномиальное дерево кучи не является обычным деревом, поскольку оно строго определено. Общее число элементов в биномиальном дереве всегда равно 2.ⁿ узлы.
Куча-сортировка: В отличие от большинства алгоритмов сортировки, пирамидальная сортировка использует для операции сортировки пространство 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 всегда перемещает его на новое место.
Просеять вниз (): этот метод сравнивает корневой объект с его дочерним элементом, а затем помещает вновь добавленный узел на его законное место.
Просеять вверх (): если вы используете метод массива для добавления нового вставленного элемента в массив, то метод Sift-Up помогает вновь добавленному узлу переместиться в новое положение. Вновь вставленный элемент сначала сравнивается с родительским путем моделирования древовидной структуры данных.
Примените формулу Parent_Index=Child_Index/2. Вы продолжаете делать это до тех пор, пока максимальный элемент не окажется в начале массива.

Базовая куча Operaных

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

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

Создать кучи

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

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

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

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

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

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

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

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

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

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

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

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

Помогает в фильтрации спама.
Реализация графовых алгоритмов.
OperaБалансировка нагрузки на систему и сжатие данных.
Найдите заказ в статистике.
Внедрите приоритетные очереди, в которых вы можете искать элементы в списке за логарифмическое время.
Структура данных кучи также используется для сортировки.
Имитация клиентов на линии.
Обработка прерываний в 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)