Hrúga (tölvunarfræði)

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita
Þessi grein fjallar um gagnagrind, ekki ruglast við kös (tölvunarfræði) sem er hluti innra minnis.
Gagnagrindur

Hrúga[1] er gagnagrind. Hægt er að hugsa sér hrúgu sem tvíundartré þar sem að sérhver hnútur er stærri eða jafn öllum hnútum í undirtrjám sínum. Það má einnig líta svo á að hnútur sé minni en eða jafn foreldri sínu, hafi það slíkt. Þessi eiginleiki er kallaður hrúgueiginleikinn. Einnig verður tréð að vera fullkomið (e. complete), það er klára verður að setja hnúta á sérhvert þrep (e. level) trésins áður en fara má á næsta þrep fyrir neðan.

Aðgerðir sem gjarnan eru framkvæmdar á hrúgur eru:

  • Eyða stærsta: Fjarlægja rótina af hrúgu.
  • Minnka gildi: Uppfæra gildi hnúts innan hrúgunnar.
  • Innsetning: Setja nýjan hnút í hrúguna.
  • Sameining: Sameina tvær hrúgur í nýja hrúgu.

Hrúga sem fylki[breyta]

Dæmi um tvíundarhrúgu.

Hægt er að geyma hrúgur sem fylki. Ef vísir (e. index) fyrsta staks hrúgunnar er 1 gildir fyrir stak X:

  • Vísir foreldris: \lfloor X/2 \rfloor
  • Vísir vinstra barns: 2 X
  • Vísir hægra barns: 2X + 1

Dæmi um hrúgu raðaða í fylki væri:

100 19 36 17 3 25 1 2 7

Tilvísanir[breyta]

Tengill[breyta]

  Þessi tölvunarfræðigrein er stubbur. Þú getur hjálpað til með því að bæta við greinina.