Структура данных «Куча»: что такое куча?

Что такое структура данных «куча»?

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

Проще говоря, куча — это полное бинарное дерево, удовлетворяющее свойству кучи: каждый родитель упорядочен последовательно относительно своих потомков, что делает её идеальной для очередей с приоритетами и сортировки кучей.

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

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

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

Типы куч

Структура данных «куча» использует различные алгоритмы для обработки вставки и удаления элементов, включая приоритетную очередь, бинарную кучу, биномиальную кучу и т. д. Сортировка кучи.

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

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

• Мин-куча – наименьшая ценность на вершине
• Макс-куча – наивысшее значение на вершине

Мин-куча

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

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

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

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

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

Макс-куча

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

Вот несколько методов, обычно используемых при реализации Java Максимальная куча:

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

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

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

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

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

Создать кучи

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

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

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

  Например, операция max-heapify проверяет, что значение родительского элемента больше, чем значение его дочернего элемента. Затем элементы можно отсортировать с помощью таких методов, как swap.ping.

• Объединение: Если вам нужно объединить две кучи в одну, используйте операцию слияния, чтобы свести значения из двух куч вместе. Исходные кучи при этом сохраняются.

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

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

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

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

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

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

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

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

• Помогает в фильтрации спама.
• Реализация алгоритмов для работы с графами, таких как алгоритмы Дейкстры и Прима.
• Operaбалансировка нагрузки системы и сжатие данных.
• Определение порядковых статистических данных, таких как k-й наименьший элемент.
• Реализация очередей с приоритетами, позволяющих искать элементы в списке за логарифмическое время.
• Структура данных «куча» также используется для сортировки с помощью алгоритма сортировки кучей.
• Имитация очереди из покупателей.
• Обработка прерываний в Operating System.
• В кодировании Хаффмана для сжатия данных.
• Обеспечение работы алгоритмов поиска в первую очередь по наилучшему варианту и эвристики A* в планировании траектории движения с помощью ИИ.

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

Следующие свойства описывают поведение очереди с приоритетами, построенной в куче:

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

Этапы реализации очереди с приоритетом кучи в Java

Следующий раздел посвящен конкретным вопросам. Java реализация, которая преобразует эти правила в работающий код.

Куча сортировки Java с Code Пример

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 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 с Code Пример

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]

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

Часто задаваемые вопросы (FAQ)