Datu struktūras Heaps, jeb Čupas

Heap, jeb Čupa var neizklausīties kā īpaši daudzsološs datu struktūras nosaukums. Tomēr tas ir ļoti svarīgs organizatoriskais
rīks un apvieno dažas citu datu struktūru funkcijas un priekšrocības.
Šajā rakstā jūs uzzināsiet par čupu struktūru un īpašībām. Jūs arī atklāsiet, kā Čupas var izmantot, lai sakārtotu elementus no vismazāk svarīgākajiem līdz vissvarīgākajiem. Un
kā, ierobežojot Čupas funkcionalitāti, var palielināt produktivitāti.
Heaps ir specializēta datu struktūra, kas tiek modelēta kā koks / tree, bet darbojas līdzīgi rindai / Queue, taču ar ievērojamu atšķirību, piešķirot
prioritāti dažiem elementiem.
Heap datu struktūra - kaudze
Katram Čupas elementam ir atslēgas vērtība (Key), un prioritāte var būt mazākā vai lielākā
atslēgas vērtība. Čupas, kurās prioritāte ir zemākās vērtības (Lowest value) atslēgai, tiek sauktas par minimālajām čupām (Min heaps) , un tās,
kurās prioritāte ir maksimālajai vērtībai (Highest value), tiek sauktas par maksimālajām čupām (Max heaps).
Min heaps, max heaps
Pirmo reizi heaps tika ieviestas kā līdzeklis efektīvai datu glabāšanai un meklēšanai. Bet kopš tā laika ir atzīts, ka ir vairākas ļoti noderīgas darbības,
kurām var piemērot heaps.
Čupai, jeb heaps ir dažas atlasītas pamatoperācijas, kuras tā var veikt,
Min_heap:
  • Insert,
  • find_min, 
  • delete_min,
Max_heap:
  • insert,
  • find_max, 
  • delete_max,
Pārējā šī raksta daļā, runāsim par minimālajām čupām, jeb min heap, taču faktiski tas pats viss arī attieksies uz maksimālo čupu – max heap.
Vienīgā atšķirība starp abām ir prioritātes noteikšana, tāpat kā daudzās šajā rakstu sērijā apspriestajās datu struktūrās. Šīs
metodes ir pamatelementi, kas veido čupu. Dažādām implementācijām dažādās valodās var būt pievienotas papildu metodes.
Gadījumā, kurā var būt samazināta atslēga ar decreaseKey(), tiek mainīta atslēgas vērtība. Motivācija būtu saistīta ar atslēgas
prioritāti reālās pasaules instanču izmaiņās.
Apspriežot kokus, tika minēts, ka binārie koki meklē vērtības pēc lieluma.
Ja vērtība ir mazāka par mezglu, ejiet pa kreiso ceļu, ja vērtība ir lielāka par mezglu, dodieties pa labo ceļu. Šīs
pamatā esošās arhitektūras dēļ Čupas bieži tiek veidotas, izmantojot bināros kokus, lai gan cita pieeja būtu panākt,
lai masīvs darbotos tādā veidā, kas atdarina binārā koka uzvedību. Minimālā vērtība tiek novietota saknes mezglā, un
katra nākamā vērtība tiek novietota hierarhijā, kur to nosaka vērtība.
Tas nozīmē, ka minimālās vērtības iegūšana no heaps ir O(1), jo tā vienmēr tiks saglabāta saknē root. Atšķirībā no stack, vērtības izgūšana neizraisa tās
pārvietošanu no koka. Tā vietā pastāv metode delete_min, ko var izsaukt, ja nolūks ir noņemt vienumus to apstrādes
laikā. Parasti Čupa neatbalsta tādas darbības kā citu vienumu dzēšana, izņemot prioritāro elementu. Iemesls ir tas, ka
Čupa ir izveidota specializētam mērķim, kas ietver vissvarīgākās preces identificēšanu un atgriešanu pēc iespējas
īsākā laikā.
Pēc tam sarindojiet nākamo svarīgo vienumu. Vienumu dzēšana kokā prasītu koka pārstrukturēšanu, un tas izraisītu veiktspējas pasliktināšanos. Ja meklējat datu struktūru, kas var darboties šādā veidā, varat apsvērt citas struktūras, nevis kaudzi. Ievietošana min heap tiek veikta pavairošanas (Propagation) ceļā. Katrs vienums tiek ievietots saknē, pēc tam tiek veikts salīdzinājums ar kreiso vērtību.
Ja tas ir mazāks par tikko ievietoto vienumu, tie tiek apmainīti, tas turpinās, līdz tikko ievietotajam vienumam nav lielākas vērtības virs tā un zemāk esošā vērtība ir mazāka. Ievietošanu čupā var panākt pēc O(log n) laika.
Tagad, kad esat izpētījis Čupas Heap pamatā esošos mehānismus, iespējams, tagad jums ir priekšstats par to, kā šo datu struktūru var izmantot. Ņemot vērā, ka tā raksturīgā struktūra piešķir prioritāti noteiktai elementu grupas vērtībai, dabiskais pielietojums būtu plānošana. Tas var attiekties uz
  • CPU – Central processing unit
  • maršrutētājiem – Routers
  • pakešu apstrādi – Packet handling
Turklāt varētu iedomāties, ka šāda struktūra būtu noderīga, lai noteiktu prioritāti noteiktiem uzdevumiem, piemēram, intervijas plānošanai, kur informācijas par kandidātu glabāšanai izmantotā atslēga var attiekties uz to, kurā intervijas procesa posmā viņi atrodas vai kāda ir lomas prioritāte organizācijā. Process, kas automātiski piemēro
grafikus, pamatojoties uz svarīgumu, var ievērojami ietaupīt laiku.
Šajā rakstā esat guvis labāku izpratni par heaps, jeb čupām un to, kā tās var izmantot, lai sakārtotu elementus no mazākajiem līdz vissvarīgākajiem. Jums ir pierādīts, ka, ierobežojot funkcionalitāti, produktivitāti var palielināt. Tāpat kā jebkuras datu struktūras atlasē, ir svarīgi atrast pareizo rīku pareizajam darbam.

Loading

Noderīgs raksts? Dalies ar citiem:
Dalīties: