Heap структура на данните: Какво е Heap? Минимална и максимална купчина (пример)

Какво е Heap?

Heap е специализирана дървовидна структура от данни. Купчината се състои от най-горния възел, наречен корен (родител). Неговото второ дете е лявото дете на корена, докато третият възел е дясното дете на корена. Последователните възли се запълват отляво надясно. Ключът на родителския възел се сравнява с този на неговото потомство и се получава правилно подреждане. Дървото е лесно за визуализиране, където всеки обект се нарича възел. Възелът има уникални ключове за идентификация.

Защо ви е необходима Heap Data Structure?

Ето основните причини за използването на Heap Data Structure:

Структурата на купчините данни позволява изтриване и вмъкване в логаритмично време – O(log₂н).
Данните в дървото се оформят в определен ред. Освен актуализиране или запитване за неща като максимум или минимум, програмистът може да намери връзки между родителя и потомството.
Можете да приложите концепцията на Обект модел на документ за да ви помогне да разберете структурата на данните в купчината.

Видове купчини

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

Приоритет-Опашка: Това е абстрактна структура от данни, съдържаща обекти с приоритет. Всеки обект или предмет има предварително определен приоритет за него. Следователно обектът или елементът с по-висок приоритет получава услугата преди останалите.
Двоична купчина: Двоичните купчини са подходящи за прости операции с купчина като изтривания и вмъквания.
Биномиална купчина: Биномиалната купчина се състои от поредица от колекции от биномни дървета, които съставят купчината. Binomial Heap дърво не е обикновено дърво, тъй като е строго дефинирано. Общият брой елементи в едно биномиално дърво винаги притежава 2ⁿ възли.
Heap-Сортиране: За разлика от повечето алгоритми за сортиране, heap-sort използва O(1) пространство за своята операция за сортиране. Това е алгоритъм за сортиране, базиран на сравнение, при който сортирането се извършва във възходящ ред, като първо се превърне в максимална купчина. Можете да гледате на Heapsort като на подобрено качествено двоично дърво за търсене.

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

Min Heap – най-малка стойност в горната част
Max Heap – най-високата стойност в горната част

Мин. купчина

В структурата на Min Heap основният възел има стойност, равна или по-малка от децата на този възел. Този възел на купчина на Min Heap съдържа минималната стойност. Като цяло, неговата min-heap структура е завършена двоично дърво.

След като имате Min heap в едно дърво, всички листа са жизнеспособни кандидати. Трябва обаче да прегледате всяко от листата, за да получите точната стойност на Max-heap.

Пример за минимална купчина

В диаграмите по-горе можете да забележите ясна последователност от корена до най-ниския възел.

Да предположим, че съхранявате елементите в Array Array_N[12,2,8,1,4]. Както можете да видите от масива, коренният елемент нарушава приоритета на Min Heap. За да поддържате свойството Min heap, трябва да извършите операциите min-heapify, за да размените елементите, докато не бъдат изпълнени свойствата Min heap.

Макс Хийп

В структурата на Max Heap родителският или коренният възел има стойност, равна или по-голяма от своите деца във възела. Този възел съдържа максималната стойност. Освен това, това е пълно двоично дърво, така че можете да изградите максимален куп от колекция от стойности и да го стартирате за O(n) време.

Ето няколко метода за внедряване на java max heap

Добавяне (): поставете нов елемент в купчина. Ако използвате масив, обектите се добавят в края на масива, докато в двоичното дърво обектите се добавят отгоре надолу и след това отляво надясно.
премахване (): Този метод ви позволява да премахнете първия елемент от списъка с масиви. Тъй като новодобавеният елемент вече не е най-големият, методът Sift-Down винаги го избутва на новото му място.
Сифт-надолу (): Този метод сравнява основен обект с неговия дъщерен обект и след това избутва новодобавения възел до правилната му позиция.
Пресяване (): ако използвате метода на масива, за да добавите нововмъкнат елемент към масив, тогава методът Sift-Up помага на новодобавения възел да се премести на новата си позиция. Нововмъкнатият елемент първо се сравнява с родителския чрез симулиране на дървовидната структура на данните.
Приложете формулата Parent_Index=Child_Index/2. Продължавате да правите това, докато максималният елемент е в предната част на масива.

Основна купчина Operaции

За да намерите най-високите и най-ниските стойности в набор от данни, ви трябват много основни операции с купчина, като намиране, изтриване и вмъкване. Тъй като елементите постоянно идват и си отиват, вие трябва:

Какво – Потърсете предмет на купчина.
Поставете – Добавете ново дете в купчината.
Изтрий – Изтриване на възел от купчина.

Създаване на купчини

Процесът на конструиране на купчини е известен като създаване на купчини. Като има списък с ключове, програмистът прави празна купчина и след това вмъква други ключове един по един, като използва основни операции с купчина.

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

Heapify: в алгоритъм за вмъкване, който помага за вмъкване на елементи в куп. Проверява се дали се следва структурата на данните за стека на свойствата.
Например, max heapify ще провери дали стойността на родителя е по-голяма от неговото потомство. След това елементите могат да бъдат сортирани с помощта на методи като размяна.

Обединяване: Като се има предвид, че имате две купчини за комбиниране в една, използвайте купчини за сливане, за да обедините стойностите от двете купчини. Все още обаче са запазени оригиналните купища.

Инспектирайте купчини

Инспектирането на купчини се отнася до проверка на броя на елементите в структурата на данните на купчината и валидиране дали купчината е празна.

Важно е да се проверяват купчините като сортиране или подреждане на елементи. Проверката дали имате елементи за обработка чрез Is-Empty() е важна. Размерът на купчината ще ви помогне да намерите максималната купчина или минималната купчина. Така че трябва да знаете елементите, следващи свойството heap.

Размер – връща величината или дължината на купчината. Можете да кажете колко елемента са в сортиран ред.
Е-празно – ако купчината е NULL, връща TRUE, в противен случай връща FALSE.

Тук отпечатвате всички елементи в приоритет Q цикъл и след това проверка дали priorityQ не е празен.

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

Използване на Heap структура от данни

Heap структурата на данните е полезна в много приложения за програмиране в реалния живот като:

Помага при филтриране на спам.
Внедряване на графични алгоритми.
Operating Балансиране на натоварването на системата и компресиране на данни.
Намерете реда в статистиката.
Внедрете опашки с приоритет, където можете да търсите елементи в списък в логаритмично време.
Heap структурата на данните се използва и за сортиране.
Симулиране на клиенти на линия.
Обработка на прекъсвания Operaтинг система.
В кодирането на Huffman за компресиране на данни.

Свойства на опашката с приоритет на Heap

В купчините с приоритети елементите от данни в списъка се сравняват един с друг, за да се определи по-малкият елемент.
Елемент се поставя в опашка и след това се премахва.
Всеки отделен елемент в опашката с приоритети има уникален номер, свързан с него, идентифициран като приоритет.
При излизане от приоритетна опашка елементът с най-висок приоритет излиза първи.

Стъпки за внедряване на опашката с приоритет на купчина в Java

Heap сортиране в 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)