Kuhja andmestruktuur: mis on kuhja? Min & Max Heap (näide)
Mis on hunnik?
Heap on spetsiaalne puu andmestruktuur. Kuhja koosneb ülemisest sõlmest, mida nimetatakse juureks (vanemaks). Selle teine laps on juure vasak laps, samas kui kolmas sõlm on juure parem laps. Järjestikused sõlmed täidetakse vasakult paremale. Vanem-sõlme võtit võrreldakse selle järglaste võtmega ja toimub õige paigutus. Puu on lihtne visualiseerida, kus iga olemit nimetatakse sõlmeks. Sõlmel on tuvastamiseks unikaalsed võtmed.
Miks vajate kuhja andmestruktuuri?
Siin on kuhja andmestruktuuri kasutamise peamised põhjused.
- Kuhja andmestruktuur võimaldab kustutamist ja sisestamist logaritmilises ajas – O(log2mitte).
- Puu andmed on kujundatud kindlas järjekorras. Lisaks selliste asjade värskendamisele või päringutele nagu maksimum või miinimum, võib programmeerija leida seoseid vanema ja järglase vahel.
- Saate rakendada kontseptsiooni Dokumendiobjekti mudel et aidata teil mõista hunniku andmestruktuuri.
Kuhjade tüübid
Kuhja andmestruktuuril on erinevad algoritmid kuhja andmestruktuuri sisestuste haldamiseks ja elementide eemaldamiseks, sealhulgas prioriteetne järjekord, binaarkuhja, kahendkuhja ja Kuhja sorteerimine.
- Prioriteedi järjekord: See on abstraktne andmestruktuur, mis sisaldab prioriteetseid objekte. Igal objektil või elemendil on selle jaoks eelnevalt paika pandud prioriteet. Seetõttu saab kõrgema prioriteediga objekt või üksus teenuse enne ülejäänut.
- Binaarne hunnik: Binaarsed kuhjad sobivad lihtsate kuhjaoperatsioonide jaoks, nagu kustutamine ja sisestamine.
- Binoomkuhja: Binoomkuhja koosneb mitmest binoompuude kogumist, mis moodustavad hunniku. Binoomkuhja puu ei ole tavaline puu, kuna see on täpselt määratletud. Binoompuu elementide koguarv on alati 2n sõlmed.
- Kuhjade sorteerimine: Erinevalt enamikust sortimisalgoritmidest kasutab kuhjasorteerimine oma sortimiseks ruumi O(1). See on võrdlusel põhinev sortimisalgoritm, kus sorteerimine toimub kasvavas järjekorras, muutes selle esmalt maksimaalseks hunnikuks. Heapsorti saate vaadata kui täiustatud kvaliteediga binaarset otsingupuud.
Tavaliselt kasutab hunniku andmestruktuur kahte strateegiat. Sisend 12 – 8 – 4 – 2 ja 1
- Min Heap – väikseim väärtus ülaosas
- Max Heap – kõrgeim väärtus ülaosas
Min hunnik
Struktuuris Min Heap on juursõlme väärtus, mis on võrdne selle sõlme alamväärtustega või väiksem. See Min Heap kuhisõlm omab minimaalset väärtust. Kokkuvõttes on selle min-hunniku struktuur terviklik binaarne puu.
Kui teil on puus Min hunnik, on kõik lehed elujõulised kandidaadid. Täpse Max-heap väärtuse saamiseks peate siiski uurima kõiki lehti.
Minimaalne kuhja näide
Ülaltoodud diagrammidel võite märgata selget järjestust juurest madalaima sõlmeni.
Oletame, et salvestate elemendid massiivi Massiivi_N[12,2,8,1,4]. Nagu massiivist näha, rikub juurelement Min Heap prioriteeti. Minimaalse kuhja omaduse säilitamiseks peate sooritama min-heapify toimingud, et elemente vahetada, kuni kuhja mini atribuudid on täidetud.
Max Heap
Max Heapi struktuuris on ülem- või juursõlme väärtus võrdne või suurem kui selle sõlmes olevad lapsed. Sellel sõlmel on maksimaalne väärtus. Lisaks on see täielik kahendpuu, nii et saate väärtuste kogust luua maksimaalse hunniku ja käivitada selle O(n) aja jooksul.
Siin on mõned meetodid java max hunniku juurutamiseks
- Lisa (): asetage uus element hunnikusse. Kui kasutate massiivi, lisatakse objektid massiivi lõppu, binaarpuus aga ülevalt alla ja seejärel vasakult paremale.
- Eemalda (): see meetod võimaldab eemaldada massiivi loendist esimese elemendi. Kuna äsja lisatud element ei ole enam kõige suurem, lükkab Sift-Down meetod selle alati uude asukohta.
- Sift-down (): see meetod võrdleb juurobjekti selle alamobjektiga ja lükkab seejärel äsja lisatud sõlme õigesse kohta.
- Sift-up (): kui kasutate massiivi äsja sisestatud elemendi massiivi lisamiseks massiivi meetodit, aitab Sift-Up meetod äsja lisatud sõlmel oma uude asukohta ümber paigutada. Värskelt sisestatud üksust võrreldakse esmalt vanemaga, simuleerides puu andmestruktuuri.
Rakendage valem Parent_Index=Child_Index/2. Jätkate seda seni, kuni maksimaalne element on massiivi esiosas.
Põhihunnik Operamine
Andmekogumi suurimate ja madalaimate väärtuste leidmiseks vajate palju põhilisi kuhjatoiminguid, nagu otsimine, kustutamine ja sisestamine. Kuna elemendid tulevad ja lähevad pidevalt, peate:
- leidma – Otsige hunnikus olevat eset.
- Sisesta – Lisage hunnikusse uus laps.
- kustutama – Kustutage sõlm kuhjast.
Loo hunnikuid
Kuhjade moodustamise protsessi tuntakse kuhjade loomisena. Klahvide loendi põhjal teeb programmeerija tühja hunniku ja lisab seejärel ükshaaval teised võtmed, kasutades põhilisi hunniku toiminguid.
Alustame min-hunniku loomist Willaimi meetodil, lisades hunnikusse väärtused 12,2,8,1 ja 4. Saate ehitada n elemendiga kuhja, alustades tühjast hunnikust ja täites selle seejärel järjestikku teiste elementidega, kasutades O (nlogn) aega.
- Kuhjas: sisestusalgoritmis, mis aitab elemente hunnikusse sisestada. Kontrollitakse, kas atribuutide hunniku andmestruktuur on esile tõstetud.
Näiteks kontrollib max heapify, kas vanema väärtus on suurem kui tema järglase väärtus. Seejärel saab elemente sorteerida, kasutades selliseid meetodeid nagu vahetamine.
- Ühenda. Arvestades, et teil on kaks hunnikut üheks ühendamiseks, kasutage kahe hunniku väärtuste ühendamiseks liitmishunnikuid. Algsed kuhjad on siiski säilinud.
Kontrollige hunnikuid
Kuhjade kontrollimine viitab kuhja andmestruktuuri elementide arvu kontrollimisele ja selle kontrollimisele, kas hunnik on tühi.
Oluline on hunnikuid kontrollida kui elementide sorteerimist või järjekorda seadmist. Is-Empty() abil on oluline kontrollida, kas teil on töödeldavaid elemente. Kuhja suurus aitab leida maksimaalse või minimaalse hunniku asukohta. Seega peate teadma hunniku omadusele järgnevaid elemente.
- SUURUS – tagastab kuhja suuruse või pikkuse. Saate öelda, mitu elementi on sorteeritud järjekorras.
- On-tühi – kui hunnik on NULL, tagastab see TRUE, vastasel juhul tagastab see FALSE.
Siin prindite kõik elemendid prioriteetQ tsüklit ja seejärel kontrollida, et priorityQ poleks tühi.
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
Kuhja andmestruktuuri kasutusalad
Kuhja andmestruktuur on kasulik paljudes päriselus programmeerimisrakendustes, näiteks:
- Aitab rämpsposti filtreerimisel.
- Graafikalgoritmide rakendamine.
- Operasüsteemi koormuse tasakaalustamine ja andmete tihendamine.
- Otsi statistikast üles järjekord.
- Rakendage prioriteetsed järjekorrad, kus saate otsida loendist logaritmilise aja järgi üksusi.
- Kuhja andmestruktuuri kasutatakse ka sortimiseks.
- Klientide simuleerimine liinil.
- Katkestage sissetöötamine Operating System.
- Huffmani kodeeringus andmete tihendamiseks.
Kuhja prioriteedijärjekorra omadused
- Prioriteetsetes hunnikutes võrreldakse loendis olevaid andmeüksusi üksteisega väiksema elemendi määramiseks.
- Element asetatakse järjekorda ja seejärel eemaldatakse.
- Igal prioriteedijärjekorra elemendil on unikaalne number, mis on sellega seotud prioriteedina.
- Prioriteedijärjekorrast väljumisel väljub esmatähtis element.
Sammud hunniku prioriteedijärjekorra juurutamiseks Java
Kuhjade sortimine JAVA-s koodinäite abil
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); } } }
Väljund
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
Hunnik Sordi sisse Python koodinäite abil
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)
Väljund
[1, 3, 4, 7, 9]
Järgmisena saate teada Poolitamise meetod
kokkuvõte
- Heap on spetsiaalne puu andmestruktuur. Kujutagem ette sugupuud koos vanemate ja lastega.
- Kuhjade andmestruktuur Java võimaldab kustutamist ja sisestamist logaritmilises ajas – O(log2mitte).
- Kuhjad sisse Python omab erinevaid algoritme kuhja andmestruktuuri sisestamiste käsitlemiseks ja elementide eemaldamiseks, sealhulgas prioriteetne järjekord, binaarkuhja, kahendkuhja ja kuhja sorteerimine.
- Struktuuris Min Heap on juursõlme väärtus, mis on võrdne või väiksem selle sõlme alamväärtustest.
- Max Heapi struktuuris on juursõlme (vanema) väärtus võrdne või suurem kui selle sõlmes olevad lapsed.
- Kuhjade kontrollimine viitab kuhja andmestruktuuri elementide arvu kontrollimisele ja selle kontrollimisele, kas hunnik on tühi.