Hrúga (tölvunarfræði)
Úr Wikipediu, frjálsa alfræðiritinu
|
|
|
Hrúga 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.
[breyta] Hrúga sem fylki
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:
- Vísir vinstra barns: 2X
- 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 |
