Структура на данните на Heap: Какво е Heap?

Какво е структура от данни тип „куп“?

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

Казано по-просто, купчината (Heap) е пълно двоично дърво, което удовлетворява свойството heap: всеки родител е подреден последователно спрямо своите деца, което го прави идеален за приоритетни опашки и сортиране по купчина (Heap Sort).

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

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

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

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

Структурата от данни Heap има различни алгоритми за обработка на вмъкване и премахване на елементи, включително приоритетна опашка, двоичен куп, биномиален куп и Сортиране на купчина.

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

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

• Мин-Хийп – най-ниска стойност на върха
• Макс-Хийп – най-висока стойност на върха

Мин-Хийп

В структурата Min-Heap, коренният възел има стойност, равна или по-малка от децата на този възел. Следователно коренът на Min-Heap съдържа минималната стойност. Min-Heap е също така пълно двоично дърво.

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

Пример за Min-Heap

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

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

Макс-Хийп

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

Ето няколко метода, които често се използват при внедряването на Java Максимална купчина:

• Добави (): Поставя нов елемент в heap. Ако използвате масив, обектите се добавят в края на масива, докато в двоичното дърво обектите се добавят отгоре надолу и след това отляво надясно.
• Премахване (): Този метод ви позволява да премахнете първия елемент от списъка с масиви. Тъй като новоповишеният елемент вече не е най-големият, методът Sift-Down винаги го премества на новото му място.
• Пресяване (): Този метод сравнява коренен обект с неговите деца и след това премества преместения възел на правилната му позиция.
• Пресяване (): Ако използвате метода array, за да добавите нововмъкнат елемент към масив, методът Sift-Up помага на новодобавения възел да се премести на правилната си позиция. Новият елемент първо се сравнява с родителския си елемент, като се симулира дървовидната структура от данни.

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

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

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

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

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

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

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

• Heapify: Рутина за вмъкване, която помага за вмъкването на елементи в heap, като същевременно запазва свойството heap.

  Например, операцията max-heapify проверява дали стойността на родителя е по-голяма от стойността на неговото потомство. След това елементите могат да бъдат сортирани с помощта на методи като swapping.

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

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

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

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

• Размер – връща големината или дължината на heap-а. Показва колко елемента са съхранени в сортиран ред.
• Е празно – връща TRUE, ако heap-ът е null, в противен случай връща FALSE.

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

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

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

Структурата от данни тип „heap“ е полезна в много програмни приложения в реалния живот, като например:

• Помага при филтриране на спам.
• Внедряване на графови алгоритми като Dijkstra и Prim.
• Operaбалансиране на натоварването на системата и компресиране на данни.
• Намиране на статистика за реда, като например k-тия най-малък елемент.
• Внедряване на опашки с приоритет, където можете да търсите елементи в списък в логаритмично време.
• Структурата от данни на купчината се използва и за сортиране чрез сортиране на купчина.
• Симулиране на клиенти, чакащи на опашка.
• Обработка на прекъсвания в Operaтинг система.
• В кодирането на Хъфман за компресиране на данни.
• Използване на метода „най-добро първо“ за търсене и A* евристики в планирането на пътища с изкуствен интелект.

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

Следните свойства описват как се държи опашката с приоритет, изградена върху heap:

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

Стъпки за внедряване на опашката с приоритет на купчината в 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]

След това ще научите за Метод на разполовяване.

Въпроси и Отговори