MAW 6.1

Ja. N?r et element blir satt inn kan vi sammenligne det med n?v?rende
minimum og endre minimum hvis det nye elementet er mindre. Men deleteMin-
operasjoner blir da kostbare.

MAW 6.2 

a) Grenen lengst til venstre har verdiene 1-3-6-15
Grenen lengst til h?yre har verdiene 1-2-4-8

b) Grenen lengst til venstre har verdiene 1-3-12-15
Grenen lengst til h?yre har verdiene 1-2-8-10

MAW 6.3

a) Grenen lengst til venstre har verdiene 4-6-13-15
Grenen lengst til h?yre har verdiene 4-5-8

b) Grenen lengst til venstre har verdiene 4-6-12-15
Grenen lengst til h?yre har verdiene 4-5-8

MAW 6.4

	a) 4N
	b) O(N^2)
	c) O(N^4.1)
	d) O(2^N)

MAW 6.10

	a) Traverser heapen prefix

Oppgave 2

	a) Vi m? holde orden p? rekkef?lgen som elementene kom inn i. Denne
	rekkef?lgen brytes i heapen - det er lett ? finne eksempler p?
	dette. Vi kan gi heapen FIFO-oppf?rsel ved ? ha en global teller som
	teller antall elementer som er satt inn i heapen. S? innf?rer vi et
	nytt felt for hvert objekt i heapen som angir verdien som den globale
	telleren hadde da objektet ble satt inn. Vi m? videre endre ordningen
	(dvs compareTo-metoden) som avgj?r om et objekt er mindre enn et annet
	slik at det f?rst sammenligner prioritetsverdien og dernest (ved lik
			prioritet) sammenligner tellerverdiene til objektene.

	b) Her m? vi bruke en hash, som skissert i boka. Mer presist lager vi
	en hashtabell som hele objektet hashes inn i. Hashtabellen inneholder
	s? en peker (indeks) til arrayen som representerer heapen, slik at vi
	kan oppdatere indeksen n?r vi rokkerer internt p? objektene i heapen.




Oppgave 4

//  OPPGAVE a:
//  Er grafen en enkel line?r liste?
//  Krav:
//  1) N?yaktig en node (sluttnoden) har ingen etterf?lger
//  2) Ingen noder har mer enn en forgjenger
//  3) Det finnes ingen l?kker

boolean liste(Node[] graf, int n) {
    // Antar at merke = 0 for alle nodene!

    Node rn, forrest;
    int i = 0;
    boolean feil = false;

    while (i < n && !feil) {
	rn = graf[i];
	if (rn.merke = 0) {
	    while (rn != null && rn.merke = 0) {
		rn.merke = 1;
		rn = rn.etterf;
	    }
	    feil = (rn != forrest);
	    forrest = graf[i];
	}
	i++;
    } 

    return (!feil);
}



// OPPGAVE b:
//  Er grafen en enkel rettet l?kke?
//  Ide: Starter i en vilk?rlig node, og f?lger etterf-pekerne til vi enten:
//  - Stopper fordi det ikke er noen etterf?lger (negativt)
//  - Har g?tt N steg (n?dvendig)
//  - Kommer tilbake til den noden vi startet i (n?dvendig)

boolean l?kke(Node[] graf, int n) {
    Node rn = graf[0].etterf;   // Starter et sted...
    int ant = 1;                // Teller graf[0];

    while (rn != null && rn != graf[1] && ant < n) {
	rn = rn.etterf;
	rn++;
    }

    return (rn == graf[0] && ant = n);
}


//  OPPGAVE c:
//  Er grafen et rotrettet tre?
//  Krav: 1) max en node uten etterf?lger
//        2) ingen l?kker (=> minst en node uten etterf?lger)
//  Hvis det finnes en l?kke, vil man fra nodene p? denne l?kken kunne
//  f?lge etterf?lgerpekerne N skritt uten ? stoppe. Dersom vi har
//  g?tt N skritt uten ? stoppe vet vi at vi m? ha en l?kke.

boolean tre(Node[] graf, int n) {
    Node rn;
    int ant = 0;
    boolean rotSett = false;

    for (int i = 0; i < n; i++) {
	rn = graf[i];

	if (rn.etterf == null) {   // Krav 1
	    if (rotSett) {
		return false;
	    } else {
		rotSett = true;
	    }
	}

	ant = 1;
	while (rn.etterf != null) {
	    if (ant = n) {
		return false;
	    } else {
		rn = rn.etterf;
		ant++;
	    }
	}
    }
    return true;
}