A Pino on täydellinen binääripuutietorakenne, joka täyttää keon ominaisuuden: jokaisen solmun lapsien arvo on pienempi tai yhtä suuri kuin sen oma arvo. Kasoja käytetään yleensä toteuttamaan prioriteettijonoja, joissa pienin (tai suurin) elementti on aina puun juuressa.

ovat malliesimerkkejä

Keon tietorakenne

Sisällysluettelo

• Kasojen tyypit
• Kasan toiminnot
• Mikä on Keon tietorakenne?

  A pino on binääripuupohjainen tietorakenne, joka täyttää keon ominaisuuden: kunkin solmun arvo on suurempi tai yhtä suuri kuin sen lapsien arvo. Tämä ominaisuus varmistaa, että juurisolmu sisältää enimmäismäärä tai minimi arvo (riippuen kasan tyypistä), ja arvot pienenevät tai kasvavat, kun liikut alas puussa.

  Kasojen tyypit

  Kasoja on kahta päätyyppiä:

  
  
  
  
  • Suurin kasa: Juurisolmu sisältää maksimiarvon, ja arvot pienenevät, kun siirryt alas puussa.
  • Vähimmäiskeko: Juurisolmu sisältää vähimmäisarvon, ja arvot kasvavat, kun siirryt alas puussa.

  Kasan toiminnot

  Yleisiä kasaoperaatioita ovat:

  • Lisää : Lisää uuden elementin kasaan säilyttäen samalla pinon ominaisuuden.
  • Ote Max/Min: Poistaa maksimi- tai minimielementin kasasta ja palauttaa sen.
  • Kasata kasaan : Muuntaa mielivaltaisen binääripuun kasaksi.

  Kasoja käytetään yleisesti prioriteettijonojen toteuttamiseen, jolloin elementit haetaan niiden prioriteetin (maksimi- tai minimiarvo) perusteella.

• Kekolajittelu on lajittelualgoritmi, joka käyttää kasaa taulukon lajitteluun nousevaan tai laskevaan järjestykseen.
• Kasoja käytetään graafialgoritmeissa, kuten Dijkstran algoritmi ja Primin algoritmi lyhimpien polkujen ja vähiten virittävien puiden löytämiseen.

Binäärikasa

Kasan sovellukset, edut ja haitat

Aika Kasan rakentamisen monimutkaisuus

Kasan ja puun vertailu

Onko kasan rakenne ainutlaatuinen, kun rakennat kasaa?

Fibonacci Kasa

Vasemmistolainen kasa

K-ary Heap

Keon lajittelu

Tarkista, onko tietty binääripuu kasa

Kuinka tarkistaa, edustaako tietty taulukko binaarikekoa?

Iteratiivinen keon lajittelu

K':n suurin elementti taulukossa

K’th Pienin/Suurin elementti lajittelemattomassa taulukossa | Sarja 1

Täydellisen binääripuun (tai kasan) korkeus N solmulla

Kasa Lajittele alenevaa järjestystä käyttämällä min kasoa

Tulosta kaikki solmut, jotka ovat pienempiä kuin arvo x Min-keossa.

Turnauspuu (voittajapuu) ja binäärikasa

Yhdistä n köyttä pienin kustannuksin

Erillisten elementtien enimmäismäärä k elementin poistamisen jälkeen

K maksimisummayhdistelmää kahdesta taulukosta

Juoksevien kokonaislukujen virran mediaani STL:n avulla

Mediaani kokonaislukuvirrassa (juoksevat kokonaisluvut)

K:nneksi suurin elementti streamissa

Suurin kolmiosainen tuote streamissa

Etsi k numeroa, joilla on eniten esiintymiä annetusta taulukosta

Muunna min-keko maksimikekoksi

Kun binaaripuun tasojärjestys kulkee, tarkista, onko puu Min-Heap

Yhdistä k lajiteltua taulukkoa | Sarja 1

Lajittele eri koneisiin tallennetut numerot

Pienin sekvenssin poikkeama

Jakson suurin poikkeama

Suurin ero kahden m elementin osajoukon välillä

Muunna BST minimikekoksi

Yhdistä kaksi binaarista Max Heapsiä

K. suurimman summan vierekkäinen alialue

K kokonaisluvun vähimmäistulo positiivisten kokonaislukujen joukossa

Järjestä merkkijonon merkit uudelleen siten, että kaksi vierekkäistä ei ole samanlaista

Kaikkien alkioiden summa k1:nnen ja k2:nnen pienimpien alkioiden välillä

Kahden taulukon numeroista muodostetun luvun vähimmäissumma

Pikalinkit:

• Harjoittele ongelmia Heapissa
• Suositus:
  • Opi tietorakenne ja algoritmit | DSA opetusohjelma