A Hoop is een volledige binaire boomdatastructuur die voldoet aan de heap-eigenschap: voor elk knooppunt is de waarde van zijn kinderen kleiner dan of gelijk aan zijn eigen waarde. Heaps worden meestal gebruikt om prioriteitswachtrijen te implementeren, waarbij het kleinste (of grootste) element altijd aan de basis van de boom staat.

stapel in ds

Heap-gegevensstructuur

Inhoudsopgave

• Soorten hopen
• Heap-operaties
• Wat is heap-gegevensstructuur?

  A hoop is een binaire boomgebaseerde datastructuur die voldoet aan de heap-eigenschap: de waarde van elk knooppunt is groter dan of gelijk aan de waarde van zijn kinderen. Deze eigenschap zorgt ervoor dat het hoofdknooppunt de maximaal of minimum waarde (afhankelijk van het type heap), en de waarden nemen af ​​of toe naarmate u verder door de boom beweegt.

  Soorten hopen

  Er zijn twee hoofdtypen hopen:

  
  
  
  

  Hoe tekenreeks naar geheel getal te converteren

  • Maximale hoop: Het hoofdknooppunt bevat de maximale waarde en de waarden nemen af ​​naarmate u verder in de boomstructuur beweegt.
  • Min hoop: Het hoofdknooppunt bevat de minimumwaarde en de waarden nemen toe naarmate u verder door de boom beweegt.

  Heap-operaties

  Veel voorkomende heap-bewerkingen zijn:

  • Invoegen : Voegt een nieuw element toe aan de heap terwijl de heap-eigenschap behouden blijft.
  • Extraheer Max/Min: Verwijdert het maximale of minimale element uit de heap en retourneert het.
  • Heapify : Converteert een willekeurige binaire boom naar een heap.

  Heaps worden vaak gebruikt om prioriteitswachtrijen te implementeren, waarbij elementen worden opgehaald op basis van hun prioriteit (maximale of minimale waarde).

• Heapsort is een sorteeralgoritme dat een heap gebruikt om een ​​array in oplopende of aflopende volgorde te sorteren.
• Heaps worden gebruikt in grafiekalgoritmen zoals Het algoritme van Dijkstra En Prim's algoritme voor het vinden van de kortste paden en minimaal opspannende bomen.

Binaire hoop

Toepassingen, voordelen en nadelen van Heap

Tijd Complexiteit van het bouwen van een hoop

Vergelijking tussen hoop en boom

Is de structuur van Heap uniek bij het bouwen van een Heap?

Fibonacci-hoop

Linkse hoop

K-ary Heap

Hoop sorteren

Controleer of een bepaalde binaire boom Heap is

Hoe controleer ik of een bepaalde array een binaire heap vertegenwoordigt?

Iteratieve heap-sortering

K'th grootste element in een array

K'th Kleinste/grootste element in ongesorteerde array | Set 1

Hoogte van een volledige binaire boom (of Heap) met N knooppunten

Heap Sorteren voor afnemende volgorde met behulp van min heap

Druk alle knooppunten met een waarde kleiner dan een waarde x af in een Min Heap.

Toernooiboom (winnaarboom) en binaire hoop

Verbind n touwen met minimale kosten

Maximaal onderscheidende elementen na het verwijderen van k-elementen

K maximale somcombinaties van twee arrays

Mediaan van stroom van lopende gehele getallen met behulp van STL

Mediaan in een stroom gehele getallen (lopende gehele getallen)

K'de grootste element in een stroom

Grootste tripletproduct in een stroom

Vind k getallen die het meeste voorkomen in de gegeven array

Converteer min-heap naar max-heap

Gegeven de niveauvolgorde van een binaire boom, controleer of de boom een ​​Min-Heap is

K gesorteerde arrays samenvoegen | Set 1

Sorteer nummers die op verschillende machines zijn opgeslagen

Kleinste verstoring van de volgorde

Grootste verstoring van een reeks

Maximaal verschil tussen twee subsets van m elementen

Converteer BST naar Min Heap

Voeg twee binaire Max Heaps samen

K-de grootste som aaneengesloten subarray

Minimumproduct van k gehele getallen in een array van positieve gehele getallen

Herschik de tekens in een tekenreeks zodanig dat geen twee aangrenzende tekens hetzelfde zijn

Som van alle elementen tussen k1'de en k2'de kleinste elementen

Minimale som van twee getallen gevormd uit cijfers van een array

Snelle links:

• Oefen problemen op Heap
• Aanbevolen:

  constructeurs in Java

  • Leer datastructuur en algoritmen | DSA-zelfstudie