Nederlands
Menu

Wat is Binaire heap (binary heap)?

Complete binaire boom waarin de waarde van elke ouder groter dan of gelijk aan (max-heap) of kleiner dan of gelijk aan (min-heap) die van zijn kinderen is. Hij kan in een array worden opgeslagen: met de wortel in a[0] zijn de kinderen van a[i] de elementen a[2i+1] en a[2i+2]. Het maximum (minimum) lezen kost O(1), invoegen en verwijderen O(log n); hij wordt gebruikt voor prioriteitswachtrijen en heapsort.

Japanse benaming: 二分ヒープ

“Binaire heap (binary heap)” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Binaire heap (binary heap)

Een binaire heap wordt opgeslagen in een array a[0], a[1], a[2], … met de wortel in a[0], waarbij elk niveau van bovenaf van links naar rechts wordt gevuld. Wat zijn de kinderen en de ouder van a[4]?

  1. AKinderen a[9] en a[10], ouder a[1]
  2. BKinderen a[8] en a[9], ouder a[2]
  3. CKinderen a[9] en a[10], ouder a[2]
Antwoord en toelichting tonen

Antwoord: A. Kinderen a[9] en a[10], ouder a[1]

Met de wortel in a[0] zijn de kinderen van a[i] de elementen a[2i+1] en a[2i+2], en is de ouder a[(i−1) ÷ 2, naar beneden afgerond]. Voor i = 4 zijn de kinderen a[9] en a[10] en is de ouder a[(4−1) ÷ 2] = a[1]. Met de wortel in a[1] zijn de kinderen a[2i] en a[2i+1] en is de ouder a[i ÷ 2]; het is dus belangrijk na te gaan welke conventie wordt gebruikt. Omdat een heap een complete binaire boom is, kan hij zonder pointers in een array worden opgeslagen, en worden ouders en kinderen alleen met indexberekeningen gevonden.

“Binaire heap (binary heap)” in de toelichting

Vragen met “Binaire heap (binary heap)” (3)

  1. Een binaire heap wordt opgeslagen in een array a[0], a[1], a[2], … met de wortel in a[0], waarbij elk niveau van bovenaf van links naar rechts wordt gevuld. Wat zijn de kinderen en de ouder van a[4]?
  2. Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?
  3. Een max-heap, waarin de waarde van elke ouder minstens zo groot is als die van zijn kinderen, wordt opgeslagen in een array met de wortel in a[0]. Aan de heap 50, 30, 40, 10, 20, 35 wordt 45 toegevoegd door de waarde achteraan te plaatsen en haar met haar ouder te verwisselen zolang ze groter is dan die ouder. Hoe ziet de array er daarna uit?

Verwante termen

Array Pointer Tijdcomplexiteit (O-notatie) Wachtrij (queue) Algoritme van Dijkstra Binair zoeken (binary search) Binaire zoekboom (binary search tree) Breedte-eerst zoeken (breadth-first search) Diepte-eerst zoeken (depth-first search) Dynamisch programmeren (dynamic programming)

Naar de woordenlijst