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 3

Sp?rsm?l 1. insert-metoden i MAW figur 6.8 side 189 tar inn et
Comparable-objekt som parameter og bruker dette objekets
compareTo-metode n?r den setter objektet inn i heapen. Event-klassen
er et slikt objekt siden det implementerer Comparable-interfacet. 

Sp?rsm?l 2. 

public class SimulationFramework {

  public void scheduleEvent (Event newEvent) 
    { eventQueue.insert(newEvent); }
  
  public void run () {
    while (! eventQueue.isEmpty()) {
      Event nextEvent = (Event) eventQueue.deleteMin();
      currentTime = nextEvent.time;
      nextEvent.processEvent();
    }
  }

  public int time () { return currentTime; }

  private int currentTime = 0;
  private BinaryHeap eventQueue = new BinaryHeap();
  // evt. angir vi en st?rrelse p? heapen som funksjon av simuleringstiden
}