Opret Hob af objekter

ArrayList er mere dynamisk end et array

i know, men hvordan indsætter jeg et reelt objekt efter prioritet i hob'en - det er mere det der er mit problem.
Hvis jeg f.eks. skulle indsætte objektet "x" bestående af (aftale, prioritet), hvordan ville min insert() (altså løkken)så skulle se ud ?

Du bruger array index som prioritet ?

vil det så sige at jeg skal bruge et 2-dimensionelt array -  skal vel have referencen med ?

En mulighed var 2 ArrayList's: en med referancer og en med prioritet

Men måske var det pænere med en ArrayList og så indsætte objekter som indeholder
2 atributter: prioritet og det egentlige objekt

det er lige præcis det jeg har leget med, men kan ikke lige få det til at spille...

Jeg havde tænkt lidt på en insert alá:

public void insert(Aftale n)
{
  currentSize++;         
  hob[currentSize] = n; 

  aftale temp                        ; 
  int i = currentSize                ; 
  int parrent = (currentSize -1 ) /2  ;


while (i > 0 && hob[i].getPriotitet < hob[parrent].getPriotitet) 
{
  temp = (Aftale) hob[i] ; 
  hob[i] = hob[parrent]  ; 
                                 
  hob[parrent] = temp ;
  i = parrent        ;                           
  parrent = (i-1)/2  ; 
}

}

- hvor en aftale består af (navn, prioritet) !

Er jeg helt forkert på den eller hvad ? :(

Jeg ville nok bare lave en ArrayList.

Aftale (navn + prioritet) bliver bare add'et.

Og enten kunne man så bare løbe igennem den ArrayList efter den højeste/laveste
prioritet når man skulle bruge den.

Eller man kunne være doven og sortere den.

pointen er at det kræver næste ingen kode at lave.

jamen, hvis vi snakker en hob, skal de pågældende aftale jo indsættes på den rigtige plads/node i selve insert-metoden.

Hvis jeg bare add'er objekterne til hoben, vil jeg jo ikkr overholde "syntaxen" for et/en heap.

Hvis det er et krav i opgaven at data skal indsættes i data strukturen efter
prioritet, så duer det naturligvis ikke.

Så vil jeg nok foreslå at du laver din egen dobbelt linket liste.

Med previous og next referancer.

Man kan vel lige så godt udnytte at array'ets index kan bruges i formlen for en hob/heap.

Altså at "parrent" til "i" kan findes ved i/2, og børnene ved 2*i og 2*i+1

Hvis du ønsker at have aftalerne i en prioriteret rækkefølge, kunne det være du skulle tage et kig på TreeSet, der er en sorteret struktur.

Så lader du klassen aftale implementere Comparable og tilføjer følgende metode på Aftale:

public int compareTo(Object o) {
  int result = 1;
  if (o instanceof Aftale) {
    Aftale a = (Aftale)o;
    if (getPriotitet() < a.getPriotitet())
      result = -1;
    else if (getPriotitet() < a.getPriotitet())
      result = 0;
  }
  return result;
}

Rettelse:

public int compareTo(Object o) {
  int result = 1;
  if (o instanceof Aftale) {
    Aftale a = (Aftale)o;
    if (getPriotitet() < a.getPriotitet())
      result = -1;
    else if (getPriotitet() == a.getPriotitet())
      result = 0;
  }
  return result;
}

Hvordan compareTo skal udformes afhænger selvfølgelig af, hvordan du angiver aftalernes prioritet. Den jeg har vist, antager at 0 er højest prioritet og højeste værdi er lavest prioritet.

Det lyder som om du gerne vil bruge en prioritetskø - her er et eksempel:
<http://olli.informatik.uni-oldenburg.de/heapsort_SALA/english/Aufgaben/Programmieren/prog_lsg.html>

Du skal bare oprette en Node klasse selv:

class AftaleNode implements Node
{
  private String aftaleNavn;
  private int prioritet;

  Node( int prioritet, aftaleNavn )
  {
      this.prioritet = prioritet;
      this.aftaleNavn = aftaleNavn;
  }

  public String getAftaleNavn()
  {
      return aftaleNavn;
  }

  public boolean isGreaterThan( Node node )
  {
      if( node instanceof AftaleNode )
      {
        return prioritet > ((AftaleNode)node).prioritet;
      }
      return false;//hmm
  }
}

dsj => Det skal implementeres vha. en minimums hob, men derfor kan jeg vel godt bruge din kode, right ?
(går ud fra at metoden skal kaldes i min while-betingelse i insert-metoden, eller...??)

ulrikm => tak for linket

men i har begge fat i noget af det jeg skal bruge, prøver lige at kigge på det, men foreløbig tak :o)...ALLE tre

Du skal ikke kalde nogen metoder. Du add'er blot Aftale-objekterne til en TreeSet-instans, og vupti ligger de i rigtig rækkefølge, defineret ud fra compareTo-metoden.

thnaks, løste det dog ved at lave en rekursiv "swap-metode" i min insert,...men jeg vil helt sikkert prøve at se om det ikke er mere optimalt med din comparableTo :o)

Håber at det er iorden at jeg splitter pointene mellem jer begge 2, efter som at det var deraf jeg fik inspirationen ;o)

ulrikm -> ligger du lige et svar

Jep