Heap

Een heap is een abstracte datastructuur in de informatica, niet te verwarren met een zogenaamd heapgeheugen. Op een heap kunnen data-elementen worden opgeslagen, maar daar ook weer uit verwijderd worden. Aan elk van de elementen is een sleutel toegewezen die de prioriteit van het element bepaalt. In veel gevallen kunnen de elementen zelf als sleutel gebruikt worden.

Afbeelding 1: De heaparray [100, 19, 36, 17, 3, 25, 1, 2, 7] weergegeven als boom.

Een heap is een array-datastructuur die een binaire boom representeert. Een array A is een heap als deze voldoet aan de heapvoorwaarde: als B een kind van A is, dan sleutel(A) ≥ sleutel(B).

Bewerkingen

Element toevoegen

Er wordt gestart met een array A met grootte N. Het te plaatsen element wordt op de plaats N+1 gezet. Op dit moment is niet noodzakelijk voldaan aan de heapvoorwaarde (het element kan groter zijn dan zijn ouder). Om terug aan de heapvoorwaarde te voldoen, worden volgende stappen herhaald totdat het element op zijn plaats staat, en dus kleiner is dan zijn ouder. Indien het toegevoegde element het grootste van de hele heap is, komt dit uiteindelijk zo in de wortel te staan.

1. Is de sleutel van het nieuwe element groter dan zijn ouder?
   1. Zo ja: Wissel ouder en het nieuwe element van plaats
   2. Zo nee: Er is nu terug voldaan aan de heapvoorwaarde en het element staat op zijn plaats.

Codevoorbeeld (C++)

template <typename T>
void HeapSort<T>::element_toevoegen(vector<T> &v, T element){
	//let op: de vector gebruikt indexen [0..N-1, de heap [1..N]
	v.push_back(element);
	int i = v.size(); //index van het nieuw toegevoegde element
	while (i > 1 && v[i - 1] > v[i/2 - 1]){ //ouder heeft index i/2
		swap(v[i - 1], v[i/2 - 1]);
		i=i/2; //het element staat nu op de plaats van zijn ouder, we starten opnieuw vanop die plaats
	}
}

Toepassingen

• Heapsort
• Prioriteitwachtrij (priority-queue)