[Inleiding programmeren] Portfolio opdracht

[Heatryn]

Hey allemaal!

Ik las hier juist de nieuwe opdracht voor het portfolio voor het practicum inleiding programmeren. Maar ik begrijp niet goed wat je daarmee moet aanvangen. Men moet iets sorteren. We geven dus een rij in van integers. Die lezen we in een array in en die moeten we dan sorteren volgens die HEAP methode. Heeft soms iemand hier al een voorbeeld van of al iets voor gedaan? Het is toch wel beetje onduidelijk wat dat sorteeralgoritme juist moet doen. Wat is trouwens een node?

Gegroet!

[Jay Jay]

Yo, heb de opdracht net afgeprint en het ziet er weer plezant uit(/end sarcasm).

Een node is volgens mij de getalwaarde in de boomstructuur, m.a.w. de waarde in de bolletjes in de boomgrafiek op pagina 2 van de opgave

Voor de rest ziet het er vrij gestructureerd uitgelegd uit, maar wss zal ik deze mening moeten herzien eens ik een eerste programmeerpoging heb ondernomen

[JoeriFranken]

ziet me er op het eerste zicht vrij ingewikkeld uit. Maar beetje zoeken kan zeker geen kwaad vooraleer er aan te beginnen

Gewoon beginnen met een paar integers in te lezen en een array te programmeren. Vandaar een beetje verderknoeien en zoeken hoe die boomstructuur er juist moet uitzien en hoe die in zijn werk zal gaan.

Maar ik snap idd niet echt goed wat een node is en wat er uiteindelijk moet gebeuren met het programma, wat het resultaat moet zijn.

[Nick]

Hmm, bizar dat hij het concept "heap" al naar voren brengt... Vorig jaar hoorde ik dat pas in het 2de semester bij GegevensStructuren
Nodes zijn inderdaad de getallen/knopen in de boomstructuur. Leaves zijn de laatste items in uw boom (das maar extra info, moete nu nx van aantrekke).
Vb:



Wat het resultaat betreft, dat moet geen grafisch geïmplementeerde boom zijn, dat zal wsl gewoon een rij gesorteerde getallen zijn.
Dus maw als output bvb (ge hoeft da uiteraard ni in 3 commando's te doen):
Heap.LeesIn 5 6 8 -4 -93 -23 -56 543~
Heap.Sorteer
Heap.Print

Output:
De gesorteerde heap:
-93 -56 -23 -4 5 6 8 543

[Jay Jay]

Jaja, probleem 1 bij de HeapSort heeft de kop opgestoken. Kan iemand me ff helpen? Ik geraak er echt nie uit.

Probleem: Ik heb het Heapify als een aparte procedure geïmplementeerd, maar wnnr ik deze procedure gebruik krijg ik de foutmelding "more actual than formal parameters." Ik heb al men parameters gecheckt maar vind geen ongebruikte parameters. dus: ?

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;

In deze procedure zou de fout dus moeten zitten, maar ik vind ze echt niet.

Alle suggesties zijn welkom

[Robbe]

Code: Select all

PROCEDURE Heapify; (* geen parameters *)

		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]; (* wel parameters EN een haakje vergeten *)
		ELSE
		END;
	END Heapify;

In deze procedure zou de fout dus moeten zitten, maar ik vind ze echt niet.

Alle suggesties zijn welkom

Is dit de juiste code wel? Zo ja, zorg dat je procedure parameters aanvaard, dit gebeurt niet vanzelf. Ook zou ik waar je je procudure oproept een ")" bijzetten...

EDIT: er zijn nog een paar foutjes, maar die vind je zelf wel Hint: wat zou er gebeuren als getallenRij een ARRAY OF REAL was geweest?

[Nick]

Uhm... is de variabele "n" een globale variabele ofwa?
Want ze staat iig ni gedeclareerd in u procedurele VAR lijst

En nogiet:
Heapify(a[index];
haakje sluiten

[Michael Cochez]

enkele opmerkingen:

Code: Select all

n := LEN(a) DIV 3;

LEN geeft niet het aantal elementen in de array, enkel de zelf gedefinieerde lengte
vb:

Code: Select all

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

Zal a de waarde 25 geven.

Je stelt ook:

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.*)

Dit klopt niet: probeer maar eens met 6 elementen in de array, daan zou je volgens deze regel slechts 2 nodes hebben.

[Heatryn]

enkele opmerkingen:

Code: Select all

n := LEN(a) DIV 3;

LEN geeft niet het aantal elementen in de array, enkel de zelf gedefinieerde lengte
vb:

Code: Select all

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

Zal a de waarde 25 geven.

Je stelt ook:

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.*)

Dit klopt niet: probeer maar eens met 6 elementen in de array, daan zou je volgens deze regel slechts 2 nodes hebben.

Zit ook vast. Heb met mijn maat even die boom bekeken en volgens hem is het niet mogelijk om een rij met een even aantal integers te sorteren volgens dat principe. Tenzij natuurlijk het niet verplicht is om op elke node twee kinderen te zetten.

[Jay Jay]

Ok thx voor de help iedereen, er rammelde nogal wat aan die code omwille van het zoeken naar een oplossing voor mijn foutmeldingen, de aangehaalde bugs zijn ondertussen al grotendeels verholpen.

Het algoritme zelf werkt nog niet, maar morgen zet ik mij der met volle moed terug achter

[Michael Cochez]

Tenzij natuurlijk het niet verplicht is om op elke node twee kinderen te zetten.

Uiteraard is dat niet verplicht, de laatste node met kinderen kan ook 1 kind hebben

[cG`]

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;

Ik zou het bovenstaande vervangen door:

Code: Select all

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

Uw fout gaat er niet weg mee zijn, maar het doet hetzelfde en het is korter dus..

Een node met slechts 1 kind mag veronderstel ik, aangezien je na het heapproces volledig doorlopen te hebben altijd een element wegneemt gebeurt dit automatisch he.

[Shinta]

ALs het kan helpen, een implementatie van een heap in Oberon :
(Bevat de heapsort niet, maar wel de heaprebuild om eensemiheap om te vormen naar een heap).

Als ge nog vragen hebt over de heap vraag jet maar (Nick zal je wel doorverwijzen)

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.

[Nick]

Lol Shinta, merci,
maar die mannen kennen nog geen pointers

Tenzij ze al op voorhand dat hebben verkend uiteraard

[Shinta]

Hmm das ook wer waar, vervangt HeapItemType door een INTEGER en negeer de dynamische array .

Tist algoritme da telt he.