Phenquestions
Illustration av Heap Data Structures
Det finns två typer av högar: en maxhög och en minhög. En max-heap-struktur är där det maximala värdet är roten och värdena blir mindre när trädet kommer ned; någon förälder är antingen lika med eller större i värde än någon av sina närmaste barn. En min-hög-struktur är där minimivärdet är roten och värdena blir större när trädet kommer ned; någon förälder är antingen lika med eller mindre i värde än någon av sina närmaste barn. I följande diagram är den första en max-heap och den andra är en min-heap:
Lägg märke till att för ett par barn så spelar det ingen roll om den till vänster är det större värdet. En rad i en nivå i trädet, måste inte nödvändigtvis fyllas från minimum till maximum, från vänster; den fylls inte nödvändigtvis från max till minimum, från vänster.
Representerar en hög i en matris
För att programvara enkelt ska kunna använda en hög måste den representeras i en matris. Max-högen ovan, representerad i en matris är:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Detta görs med början med rotvärdet som det första värdet för matrisen. Värdena placeras kontinuerligt genom att läsa trädet från vänster till höger, från topp till botten. Om ett element saknas hoppas dess position i matrisen över. Varje nod har två barn. Om en nod är vid index (position) n, är dess första underordnade i matrisen vid index 2n + 1, och dess nästa barn är vid index 2n + 2. 89 är vid index 0; sitt första barn, 85 är i index 2 (0) + 1 = 1 medan det andra barnet är i index 2 (0) + 2 = 2. 85 är vid index 1; dess första barn, 84, är i index 2 (1) + 1 = 3 medan det andra barnet, 82 är i index 2 (1) + 2 = 4. 79 är vid index 5; sitt första barn, 65 är vid index 2 (5) + 1 = 11 medan det andra barnet är i index 2 (5) + 2 = 12. Formlerna tillämpas på resten av elementen i matrisen.
En sådan matris, där innebörden av ett element och förhållandet mellan elementen, antyds av elementets position, kallas en implicit datastruktur.
Den implicita datastrukturen för ovanstående minhög är:
65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89Ovanstående max-heap är ett komplett binärt träd men inte ett fullständigt binärt träd. Det är därför som vissa platser (positioner) är tomma i matrisen. För ett fullständigt binärt träd kommer ingen plats att vara tom i matrisen.
Om högen nu var ett nästan komplett träd, till exempel om värdet 82 saknades, skulle matrisen vara:
89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69I den här situationen är tre platser tomma. Formlerna är dock fortfarande tillämpliga.
Operationer
En datastruktur är ett dataformat (t.ex.g. ett träd), plus förhållandet mellan värdena, plus operationerna (funktionerna) som utförs på värdena. För en hög är förhållandet som går genom hela högen att föräldern måste vara lika eller större i värde än barnen för en maxhög; och föräldern måste vara lika eller mindre i värde än barnen för en min hög. Detta förhållande kallas högegenskapen. Verksamheten på en hög grupperas under rubrikerna Skapelse, Grundläggande, Internt och Inspektion. En sammanfattning av högens verksamhet följer:
Heap Operations Sammanfattning
Det finns vissa programvaruoperationer som är vanliga med massor, enligt följande:
Skapande av en hög
create_heap: Att skapa en hög betyder att du bildar ett objekt som representerar högen. På C-språket kan du skapa en hög med objekttypen struct. En av medlemmarna i strukturen kommer att vara heap array. Resten av medlemmarna kommer att vara funktioner (operationer) för högen. Create_heap betyder att skapa en tom hög.
Heapify: Heap-arrayen är en delvis sorterad (ordnad) array. Heapify betyder, ange en heap-array från en osorterad array - se detaljer nedan.
Sammanfoga: Detta innebär att du bildar en facklig hög från två olika högar - se detaljer nedan. De två högarna ska båda vara maxhöga eller båda minhöga. Den nya högen överensstämmer med högegenskapen, medan de ursprungliga högarna bevaras (inte raderas).
Sammanfogat: Detta innebär att du går med i två högar av samma typ för att bilda en ny, med dubbletter - se detaljer nedan. Den nya högen överensstämmer med högegenskapen, medan de ursprungliga högarna förstörs (raderas). Huvudskillnaden mellan sammanslagning och smältning är att för smältning passar ett träd som ett underträd till roten till det andra trädet, vilket möjliggör dubbla värden i det nya trädet, medan för sammanslagning bildas ett nytt högträd som tar bort dubbletter. Det finns inget behov av att underhålla de två originalhögarna med smältning.
Grundläggande höghantering
find_max (find_min): Leta upp maxvärdet i max-heap-matrisen och returnera en kopia, eller leta upp minimivärdet i min-heap-arrayen och returnera en kopia.
Infoga: Lägg till ett nytt element i heapmatrisen och ordna om matrisen så att heapegenskapen i diagrammet bibehålls.
extract_max (extract_min): Leta upp maxvärdet i max-heap-arrayen, ta bort och returnera det; eller lokalisera minimivärdet i min-heap-arrayen, ta bort och returnera det.
delete_max (delete_min): Leta reda på rotnoden på en max-heap, som är det första elementet i max-heap-arrayen, ta bort den utan att nödvändigtvis returnera den; eller lokalisera rotnoden på en minhög, som är det första elementet i minhögmatrisen, ta bort den utan att nödvändigtvis returnera den;
Byt ut: Leta reda på rotnoden på endera högen, ta bort den och ersätt den med en ny. Det spelar ingen roll om den gamla roten returneras.
Intern högdrift
öka_nyckel (minska_nyckel): Öka värdet på vilken nod som helst för en max-heap och ordna om så att heap-egenskapen upprätthålls, eller minska värdet på vilken nod som helst för en min-heap och ordna om så att heap-egenskapen bibehålls.
Radera: ta bort vilken nod som helst och ordna sedan om så att egenskapen heap bibehålls för max-heap eller min-heap.
shift_up: flytta en nod uppåt i en max-heap eller min-heap så länge som behövs, ordna om för att bibehålla heap-egenskapen.
shift_down: flytta en nod ner i en max-heap eller min-heap så länge som behövs, ordna om för att bibehålla heap-egenskapen.
Inspektion av en hög
Storlek: Detta returnerar antalet nycklar (värden) i en hög; det inkluderar inte de tomma platserna i heapmatrisen. En hög kan representeras av kod, som i diagrammet, eller med en matris.
är tom: Detta returnerar Boolean true om det inte finns någon nod i en hög eller Boolean false om högen har minst en nod.
Sikt i en hög
Det siktas upp och siktas ner:
Sift-Up: Det betyder att byta en nod med sin förälder. Om heapegenskapen inte är nöjd, byt förälder med sin egen förälder. Fortsätt på detta sätt i vägen tills heapegenskapen är uppfyllt. Proceduren kan nå roten.
Sikt ner: Det betyder att byta en nod av stort värde med det mindre av sina två barn (eller ett barn för en nästan fullständig hög). Om heap-egenskapen inte är nöjd, byt ut den nedre noden med den mindre noden för sina egna två barn. Fortsätt på detta sätt i vägen tills heapegenskapen är nöjd. Förfarandet kan nå ett blad.
Heapifying
Heapify betyder att sortera en osorterad array för att ha heap-egenskapen nöjd för max-heap eller min-heap. Det betyder att det kan finnas några tomma platser i den nya matrisen. Den grundläggande algoritmen för att heapify en max-heap eller min-heap är som följer:
- om rotnoden är mer extrem än någon av dess barns nod, byt sedan roten med den mindre extrema undernoden.
- Upprepa detta steg med barnens noder i ett förbeställningsschema för trädträd.
Det sista trädet är ett högt träd som uppfyller högegenskapen. En hög kan representeras som ett träddiagram eller i en matris. Den resulterande högen är ett delvis sorterat träd, dvs.e. en delvis sorterad matris.
Heap Operation Detaljer
Det här avsnittet i artikeln ger detaljer om heap-operationerna.
Skapande av en höguppgifter
skapa_heap
Se ovan!
heapify
Se ovan
sammanfoga
Om högen arrays,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69och
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71slås samman, kan resultatet utan dubbletter bli,
89, 85, 87, 84, 82, 83, 81, 80, 79,, 73, 68, 65, 69, 70, 71Efter lite siktning. Lägg märke till att 82 i den första gruppen inte har några barn. I den resulterande matrisen är den vid index 4; och dess positioner vid index 2 (4) + 1 = 9 och 2 (4) + 2 = 10 är lediga. Det betyder att det inte heller har barn i det nya träddiagrammet. De två ursprungliga högen bör inte tas bort eftersom deras information inte finns i den nya högen (ny matris). Den grundläggande algoritmen för att slå samman högar av samma typ är följande:
- Gå med i en matris till botten av den andra matrisen.
- Heapify eliminerar dubbletter och ser till att noder som inte hade barn i de ursprungliga högarna fortfarande inte har barn i den nya högen.
smälta
Algoritmen för att smälta två högar av samma typ (antingen två max- eller två min-) är följande:
- Jämför de två rotnoderna.
- Gör den mindre extrema roten och resten av dess träd (subtree), det andra barnet till den extrema roten.
- Sikt det vilse barnet från roten till nu den extrema subtree, nedåt i den extrema subtree.
Den resulterande högen är fortfarande i överensstämmelse med högegenskapen, medan de ursprungliga högarna förstörs (raderas). De ursprungliga högarna kan förstöras eftersom all information de hade finns fortfarande i den nya högen.
Grundläggande höghantering
find_max (find_min)
Detta innebär att du hittar det maximala värdet i max-heap-matrisen och returnerar en kopia, eller lokaliserar minimivärdet i min-heap-arrayen och returnerar en kopia. En heap-array tillåter per definition redan heap-egenskapen. Så returnera bara en kopia av det första elementet i matrisen.
Föra in
Detta innebär att du lägger till ett nytt element i heapmatrisen och ordnar om arrayen så att heapegenskapen i diagrammet bibehålls (nöjd). Algoritmen för att göra detta för båda typerna av högar är som följer:
- Anta ett fullständigt binärt träd. Detta innebär att matrisen måste fyllas i slutet med tomma platser om det behövs. Det totala antalet noder för en hel hög är 1, eller 3 eller 7 eller 15 eller 31, etc.; fortsätt att fördubblas och lägga till 1.
- Sätt noden på den lämpligaste tomma platsen efter storlek, mot slutet av högen (mot slutet av höguppsättningen). Om det inte finns någon tom plats startar du en ny rad längst ner till vänster.
- Sikt upp om det behövs tills heapegenskapen är nöjd.
extrahera_max (extrahera_min)
Leta upp maxvärdet i max-heap-matrisen, ta bort och returnera det; eller lokalisera minimivärdet i min-heap-arrayen, ta bort och returnera det. Algoritmen till extract_max (extract_min) är som följer:
- Ta bort rotnoden.
- Ta (ta bort) den nedre högra noden (den sista noden i matrisen) och placera den vid roten.
- Sikt ner efter behov, tills heapegenskapen är nöjd.
delete_max (delete_min)
Leta reda på rotnoden till en max-heap, som är det första elementet i max-heap-arrayen, ta bort den utan att nödvändigtvis returnera den; eller lokalisera rotnoden på en minhög, som är det första elementet i minhögmatrisen, ta bort den utan att nödvändigtvis returnera den. Algoritmen för att radera rotnoden är som följer:
- Ta bort rotnoden.
- Ta (ta bort) den nedre högra noden (den sista noden i matrisen) och placera den vid roten.
- Sifta ner efter behov tills heapegenskapen är nöjd.
byta ut
Leta reda på rotnoden för endera högen, ta bort den och ersätt den med den nya. Det spelar ingen roll om den gamla roten returneras. Sikt ner om så är lämpligt, tills heapegenskapen är nöjd.
Intern högdrift
öka_nyckel (minska_nyckel)
Öka värdet på vilken nod som helst för en max-heap och ordna om så att heap-egenskapen bibehålls, eller minska värdet på en nod för en min-heap och ordna om så att heap-egenskapen bibehålls. Sikt uppåt eller nedåt efter behov tills heapegenskapen är nöjd.
radera
Ta bort den intressanta noden och ordna sedan om så att heapegenskapen bibehålls för max-heap eller en min-heap. Algoritmen för att radera en nod är som följer:
- Ta bort den intressanta noden.
- Ta (ta bort) den nedre längst till höger noden (sista noden i matrisen) och placera vid indexet för den borttagna noden. Om den raderade noden befinner sig i den sista raden kanske det inte är nödvändigt.
- Sikt uppåt eller nedåt efter behov tills heapegenskapen är nöjd.
växla upp
Flytta en nod uppåt i en max-heap eller min-heap så länge som behövs, ordna om för att bibehålla heap-egenskapen - sikt upp.
växla ner
Flytta en nod nedåt i en max-heap eller min-heap så länge som behövs, ordna om för att bibehålla heap-egenskapen - sikt ner.
Inspektion av en hög
storlek
Se ovan!
är tom
Se ovan!
Andra klasser av högar
Högen som beskrivs i denna artikel kan betraktas som den huvudsakliga (allmänna) högen. Det finns andra klasser av högar. De två som du borde veta utöver detta är dock Binary Heap och d-ary Heap.
Binär hög
Den binära högen liknar den här huvuden, men med fler begränsningar. I synnerhet måste den binära högen vara ett komplett träd. Förväxla inte mellan ett komplett träd och ett fullt träd.
d-ary Heap
En binär hög är en 2-arig hög. En hög där varje nod har 3 barn är en 3-arig hög. En hög där varje nod har 4 barn är en 4-arig hög, och så vidare. En d-ary-hög har andra begränsningar.
Slutsats
En hög är ett komplett eller nästan fullständigt binärt träd som uppfyller högegenskapen. Heap-egenskapen har två alternativ: för en max-heap måste en förälder vara lika med eller större i värde än de omedelbara barnen; för en minhög måste en förälder vara lika med eller mindre i värde än de närmaste barnen. En hög kan representeras som ett träd eller i en matris. När den representeras i en matris är rotnoden den första noden i matrisen; och om en nod är vid index n, är dess första underordnade i matrisen vid index 2n + 1 och dess nästa barn är vid index 2n + 2. En hög har vissa operationer som utförs på matrisen.
Chrys
