WINAK

Code: Select all

PROCEDURE Heapify;

		VAR
			a,b:getallenRij;
			grootsteKind:INTEGER;
			tijdelijk: INTEGER;
			index:INTEGER;
			kind1, kind2:INTEGER;

	BEGIN
		n := LEN(a) DIV 3;
		(* Elke node heeft 2 kinderen die ook plaatsen in de array hebben, 
		dus als je de lengte van de array deelt door 3 bekom je het aantal nodes.*)
		kind1 := 2*index+1;
		kind2 := 2*index+2;
		IF (a[kind1] > a[kind2]) THEN
			a[kind1] := grootsteKind;
		ELSIF (a[kind1] < a[kind2]) THEN
			a[kind2] := grootsteKind;
		ELSIF (a[kind1] = a[kind2]) THEN
			a[kind1] := grootsteKind;
		END;
		IF (a[index] < a[grootsteKind]) THEN
			tijdelijk := index;
			index := grootsteKind;
			grootsteKind := tijdelijk;
			Heapify(a[index];
		ELSE
		END;
	END Heapify;

Code: Select all

n := LEN(a) DIV 3;

Code: Select all

VAR
  mijnarray : ARRAY 25 OF INTEGER
BEGIN
  a:=LEN (mijnarray);

Code: Select all

(* Elke node heeft 2 kinderen die ook plaatsen in de array hebben, dus als je de lengte van de array deelt door 3 bekom je het aantal nodes.*)

Code: Select all

		IF (a[kind1] > a[kind2]) THEN
			a[kind1] := grootsteKind;
		ELSIF (a[kind1] < a[kind2]) THEN
			a[kind2] := grootsteKind;
		ELSIF (a[kind1] = a[kind2]) THEN
			a[kind1] := grootsteKind;
		END;

Code: Select all

		IF (a[kind1] >= a[kind2]) THEN
			a[kind1] := grootsteKind;
		ELSIF (a[kind1] < a[kind2]) THEN
			a[kind2] := grootsteKind;
		END;

Code: Select all

MODULE Heap;
(*
	Author : Kristof Overdulve
	Date : 18/04/2006
	Description : Implementation of a heap 
*)

	IMPORT
		OutExt;

	TYPE
		Heap* = POINTER TO HeapDesc;
		HeapDesc* =
			RECORD
				size : INTEGER;
				items : HeapArr;
			END;
			
	
		HeapArr = POINTER TO HeapArrDesc;
		HeapArrDesc = ARRAY OF HeapItemType;
		
		HeapItemType* = POINTER TO HeapItemTypeDesc;
		HeapItemTypeDesc* = 
			RECORD
				key : INTEGER;
			END;
			
	(* ------------------------------------------------------------------ *)
			
	PROCEDURE (this : Heap) createHeap* (maxitems : INTEGER);
	(** Cre‘ert een heap *)
	
	BEGIN
		this^.size := 0;
		NEW (this^.items, maxitems);
	END createHeap;
	
	(* ------------------------------------------------------------------ *)

	PROCEDURE (this : Heap) destroyHeap* ();
	(** Vernietigt een heap *)
	
	BEGIN
		this^. size := 0;
		this^.items := NIL;
	END destroyHeap;
	
	(* ------------------------------------------------------------------ *)

	PROCEDURE (this : Heap) heapIsEmpty* () : BOOLEAN;
	(** Geeft aan of de heap leeg is *)
	
	BEGIN
		RETURN (this^.size = 0);
	END heapIsEmpty;
	
	(* ------------------------------------------------------------------ *)
	
	PROCEDURE (this : Heap) heapInsert* (newItem : HeapItemType; VAR succes 												: BOOLEAN);
	(** Voegt een nieuw item toe aan de heap *)
	
		VAR
			temporary : HeapItemType;		
			place, parent : INTEGER;	
	
	BEGIN
		(* Controleert of de sleutel zich al in de heap bevindt of dat de 			input verkeerd is *)
		IF (this^.heapContainsKey (newItem.key) OR (newItem = NIL)) THEN
		
			(* sleutel is gevonden, dit mag niet *)
			succes := FALSE;
			
		ELSE	
			(* succes op waar instellen *)
			succes := TRUE;
			
			(* Voegt newItem toe aan het einde van de heap *)
			this^.items[this^.size] := newItem;
			
			(* Bepaalt de posities van het item en van zijn ouder *)
			place := this^.size;
			parent := (place-1) DIV 2;
			
			(* Trickle-up *)
			WHILE (((place-1)/2 >= 0) & (this^.items[place].key > 						this^.items[parent].key)) DO
			
				(* Verwissel ouder en kind *)
				temporary := this^.items[place];
				this^.items[place] := this^.items[parent];
				this^.items[parent] := temporary;
				
				(* update posities *)
				place := parent;
				parent := place DIV 2;
			
			END;	(* WHILE *)
			
			(* incrementeer de grootte van de heap *)
			INC(this^.size);
			
		END;	(* IF *)
	END heapInsert;

	(* ------------------------------------------------------------------ *)
	
	PROCEDURE (this : Heap) heapDelete* (VAR item : HeapItemType; VAR succes 												: BOOLEAN);
	(** Verwijdert het item met de hoogste sleutel uit de heap en keert dat 	item terug *)
	
		VAR
			rootItem : HeapItemType;
	
	BEGIN	
		(* Initialiseer het item op NIL *)
		item := NIL;
		
		(* De grootte moet groter zijn dan 0 *)
		IF (this^.size > 0) THEN
			(* Stel succes in op waar *)
			succes := TRUE;
		
			(* Geef het item in de root weer *)
			rootItem := this^.items[0];
			
			(* Kopieer het item van de laatste node naar de root *)
			this^.items[0] := this^.items[this^.size-1];
			
			NEW(item);
			item := this^.items[this^.size-1];
		
			(* Verwijder de laatste node *)
			DEC(this^.size);
			
			(* Maak van de semiheap opnieuw een heap *)
			IF (this^.size > 0) THEN
				this^.heapRebuild (0);
			END;
		
		ELSE	(* de heap is leeg *)
			(* Stel succes in op vals *)
			succes := FALSE;
		END;	(* IF*)			
	END heapDelete;
	
	(* ------------------------------------------------------------------ *)
	
	PROCEDURE (this : Heap) heapRebuild* (root : INTEGER);
	(** Maakt van een semiheap opnieuw een heap *)
	
		VAR
			child, rightChild : INTEGER;
			temporary : HeapItemType;
	
	BEGIN
		(* Als de root geen blad is *)
		IF (root * 2 + 1 <= this^.size - 1) THEN		
			(* Stel de positie van het linkerkind in *)
			child := 2 * root + 1;

			(* Als er een rechterkind is *)
			IF (child + 1 <= this^.size - 1) THEN				
				rightChild := child + 1;
				
				(* Stel child in op de positie van het grootste kind van de 				root *)
				IF (this^.items[rightChild].key > this^.items[child].key) THEN
					child := rightChild;
				END;	(* IF*)
			END;	(* IF *)

			(* Als het item van de wortel een kleinere waarde heeft dan het 			item van zijn grootste kind worden de items verwisseld *)
			
			IF (this^.items[root]^.getKey() < this^.items[child]^.getKey()) 			THEN
				(* Verwissel de root en zijn kind *)
				
				temporary := this^.items[root];
				this^.items[root] := this^.items[child];
				this^.items[child] := temporary;
				
				(* Bouw de semiheap opnieuw om met wortel child *)
				this^.heapRebuild (child);
				
			END;	(* IF *)
		END;	(* IF *)
	END heapRebuild;
	
	(* ------------------------------------------------------------------ *)

	PROCEDURE (this : Heap) heapContainsKey* (key : INTEGER) : BOOLEAN;
	(** Controleert of de heap reeds over een key-waarde, gelijk aan key 	beschikt *)
	
		VAR
			count : INTEGER;
			keyfound : BOOLEAN;
			
	BEGIN
		(* Neem aan dat de heap geen element bevat met die key-waarde *)
		keyfound := FALSE;
						
		(* Loop alle elementen af *)
		FOR count := 0 TO (this^.size-1) DO		
			IF (this^.items[count].key = key) THEN	
				keyfound := TRUE;
			END;	(* IF *)
		END;	(* count *)
		
		(* Keer keyfound terug *)
		RETURN keyfound;
	END heapContainsKey;	
							
	(* ------------------------------------------------------------------ *)

	PROCEDURE (this : Heap) createHeapItem* (key : INTEGER) : HeapItemType;
	(** Creeert een nieuw item aan de hand van een waarde *)
	
		VAR
			item : HeapItemType;
	
	BEGIN
		NEW(item);
		item.key := key;
		
		(* Keert het item terug *)
		RETURN item;
	END createHeapItem;
	
	(* ------------------------------------------------------------------ *)

	PROCEDURE (this : HeapItemType) getKey* () : INTEGER;
	(** Vraagt de key van het item HeapItemType op *)
	
	BEGIN
		RETURN (this^.key);
	END getKey;
	
BEGIN
END Heap.