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

Що таке Heap?

Купа — це спеціалізована структура даних дерева. Купа містить верхній вузол, який називається коренем (батьківським). Його другий дочірній елемент є лівим дочірнім елементом кореня, тоді як третій вузол є правим дочірнім елементом кореня. Послідовні вузли заповнюються зліва направо. Ключ батьківського вузла порівнюється з ключем його нащадків, і відбувається належне розташування. Дерево легко візуалізувати, де кожна сутність називається вузлом. Вузол має унікальні ключі для ідентифікації.

Навіщо вам потрібна структура даних купи?

Ось основні причини використання Heap Data Structure:

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

Типи куп

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

Пріоритет-черга: Це абстрактна структура даних, що містить пріоритетні об’єкти. Для кожного об’єкта чи предмета заздалегідь встановлено пріоритет. Таким чином, об’єкт або елемент, якому призначено вищий пріоритет, отримує послугу перед іншими.
Двійкова купа: Бінарні купи підходять для простих операцій із купою, таких як видалення та вставки.
Біноміальна купа: Біноміальна купа складається з ряду колекцій біноміальних дерев, які утворюють купу. Біноміальне дерево купи не є звичайним деревом, оскільки воно строго визначене. Загальна кількість елементів у біноміальному дереві завжди дорівнює 2ⁿ вузли.
Сортування купи: На відміну від більшості алгоритмів сортування, heap-sort використовує простір O(1) для своєї операції сортування. Це алгоритм сортування на основі порівняння, де сортування відбувається в порядку зростання, спочатку перетворюючись на максимальну купу. Ви можете дивитися на Heapsort як на вдосконалене якісне бінарне дерево пошуку.

Як правило, структура даних купи використовує дві стратегії. Для введення 12 – 8 – 4 – 2 і 1

Min Heap – найменше значення вгорі
Max Heap – найвище значення вгорі

Мінімальна купа

У структурі мінімальної купи кореневий вузол має значення, що дорівнює або менше, ніж дочірні елементи цього вузла. Цей вузол купи мінімальної купи містить мінімальне значення. Загалом, його структура min-heap завершена двійкове дерево.

Якщо у вас є купа Min на дереві, усі листки є життєздатними кандидатами. Однак вам потрібно перевірити кожен із листів, щоб отримати точне значення Max-heap.

Приклад мінімальної купи

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

Припустімо, ви зберігаєте елементи в масиві Array_N[12,2,8,1,4]. Як ви бачите з масиву, кореневий елемент порушує пріоритет Min Heap. Щоб підтримувати властивість мінімальної купи, вам потрібно виконати операції min-heapify, щоб поміняти елементи місцями, доки не будуть досягнуті властивості мінімальної купи.

Макс Хіп

У структурі Max Heap батьківський або кореневий вузол має значення, яке дорівнює або перевищує його дочірні вузли у вузлі. Цей вузол містить максимальне значення. Крім того, це повне двійкове дерево, тому ви можете створити максимальну купу з набору значень і запустити її за O(n) раз.

Ось декілька методів реалізації максимальної купи Java

Додати (): помістити новий елемент у купу. Якщо ви використовуєте масив, об’єкти додаються в кінці масиву, тоді як у бінарному дереві об’єкти додаються зверху вниз, а потім зліва направо.
Видалити (): Цей метод дозволяє видалити перший елемент зі списку масиву. Оскільки щойно доданий елемент більше не є найбільшим, метод Sift-Down завжди переміщує його на нове місце.
Просіяти (): цей метод порівнює кореневий об’єкт із його дочірнім об’єктом, а потім переміщує щойно доданий вузол у належне положення.
Sift-Up (): якщо ви використовуєте метод array для додавання щойно вставленого елемента до масиву, тоді метод Sift-Up допоможе щойно доданому вузлу переміститися на нове місце. Щойно вставлений елемент спочатку порівнюється з батьківським шляхом імітації структури даних дерева.
Застосуйте формулу Parent_Index=Child_Index/2. Ви продовжуєте робити це, доки максимальний елемент не опиниться на початку масиву.

Базова купа Operaвих

Щоб знайти найвище та найнижче значення в наборі даних, вам знадобиться багато базових операцій із купою, таких як пошук, видалення та вставлення. Оскільки елементи постійно приходять і йдуть, ви повинні:

знайти – Шукайте предмет у купі.
Insert – Додати нову дитину в купу.
видаляти – Видалити вузол із купи.

Створення куп

Процес створення куп відомий як створення куп. Отримавши список ключів, програміст створює порожню купу, а потім вставляє інші ключі по одному за допомогою базових операцій із купою.

Отже, давайте почнемо будувати Min-heap за допомогою методу Willaim, вставляючи значення 12,2,8,1 і 4 у купу. Ви можете створити купу з n елементів, починаючи з порожньої купи, а потім послідовно заповнюючи її іншими елементами, використовуючи час O (nlogn).

Heapify: в алгоритмі вставки, який допомагає вставляти елементи в купу. Перевіряє, чи дотримується структура даних купи властивостей.
Наприклад, max heapify перевірить, чи значення батьківського елемента більше, ніж його нащадок. Потім елементи можна сортувати за допомогою таких методів, як обмін.

Злиття: враховуючи, що у вас є дві купи для об’єднання в одну, використовуйте купи злиття, щоб об’єднати значення з двох куп. Однак оригінальні терикони досі збереглися.

Огляньте відвали

Перевірка купи стосується перевірки кількості елементів у структурі даних купи та перевірки того, чи купа порожня.

Важливо перевіряти купи як сортування або чергування елементів. Перевірка, чи є у вас елементи для обробки використання is-Eronty (). Розмір купи допоможе знайти максимальну або мінімальну купу. Отже, вам потрібно знати елементи, що йдуть за властивістю heap.

Розмір – повертає величину або довжину купи. Ви можете визначити, скільки елементів упорядковано.
Пусто – якщо купа дорівнює 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)