Hrúga (tölvunarfræði)

Þessi grein er um gagnagrind. Ekki ruglast við kös (tölvunarfræði) sem er hluti innra minnis.

Gagnagrindur

Fylki Tengdur listi Hringtengdir listar Fjöltengdir listar Tré B-tré 2-3-4 tré Rauðsvört tré Biðraðir FIFO Hlaði Hrúga

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.

Hrúga sem fylki

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: $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

Tengill

• What is a heap data structure? Geymt 15 maí 2006 í Wayback Machine

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