Guten Tag Community,
ich habe eine Hausaufgabe von der Uni, die ich bearbeiten muss und habe Verständnisprobleme, wie ich an die Sache rangehen soll. Ich lade mal die Datei hoch, damit ihr euch einmal die Aufgabenstellung durchlesen könnt. Meine Frage bezieht sich nicht auf die einzelnen Methoden, sondern wie ich das grundsätzliche Konstrukt schreiben soll. Hier mein vorläufiger Code:
Ich weiß das ist alles noch sehr wirr und in der Entwicklungsphase, aber ich verstehe die genaue Herangehensweise nicht. Mir geht es vorsätzlich nur um die Methode peek() und das gesamte Konstrukt (die anderen Methode bitte nicht beachten, ist sowieso noch alles falsch). Ich möchte erst einmal verstehen, wie ich mit dieser ArrayList grundsätzlich arbeiten soll. wenn ich zum Beispiel den Befehl "System.out.println(a.peek());" ausführen möchte, funktioniert das nicht, weil "peek()" nicht für "ArrayList<Integer>" definiert worden ist. Und meine Frage ist, wie kann ich den nun die Methode "peek()" denn noch schreiben, um beispielsweise auf das erste oder auch letzte Element zuzugreifen, ohne den Rückgabewert zu verändern. Die einzelnen Methode sind mir auch noch durch das Interface gegeben worden. Hier das Interface:
Das mag vielleicht jetzt alles auf einmal viel erscheinen, doch ich möchte nur zum Verständnis wissen, ob ich denn nun den Konstruktor ändern muss oder "private ArrayList<Entry> entryList;". Den Rest zu schreiben ist grundsätzlich nicht schwer und die Aufgabe an sich leicht, bloß ich verstehe nicht, wie ich das Grundgerüst schreiben soll, um überhaupt anfangen zu können. Danke im Voraus.
P.S.: Tut mir leid, dass es ein derart langer Post ist und sehr viel Informationen vorhanden sind, bloß ich poste lieber sehr viel Information rein, um vorläufige Fragen zu klären.
ich habe eine Hausaufgabe von der Uni, die ich bearbeiten muss und habe Verständnisprobleme, wie ich an die Sache rangehen soll. Ich lade mal die Datei hoch, damit ihr euch einmal die Aufgabenstellung durchlesen könnt. Meine Frage bezieht sich nicht auf die einzelnen Methoden, sondern wie ich das grundsätzliche Konstrukt schreiben soll. Hier mein vorläufiger Code:
Java:
public class PriorityQueue<E, EntryType> implements PQInterface<E> {
private class Entry{
public int prio;
public EntryType value;
public Entry(EntryType value){
prio = 0;
this.value = value;
}
}
private ArrayList<Entry> entryList;
public PriorityQueue(){
entryList = new ArrayList<>();
}
private int getLeftChildIndex(int index){
return 2*index;
}
private int getRightChildIndex(int index){
return 2*index+1;
}
private int getParentIndex(int index){
return (index/2);
}
private void bubbleUp(int index){
// int parIndex = getParentIndex(index);
// int pos = index -1;
// while((pos > 0) && (pos/2 > pos)){
// pos /=2;
// }
// while (index > 0 && entryList.get(parIndex).prio > entryList.get(index).prio) {
// swap(parIndex, index);
// index = parIndex;
// parIndex = getParentIndex(index);
// }
//
// entryList.set(0, entryList.get(index)); // Acts as sentinal so we don't fall off the array
//
// int parent = index / 2;
//
// while (entryList.get(parent) entryList.get(index)) {
//
// Entry temp = entryList.get(parent);
//
// entryList.set(parent, entryList.get(index));
//
// entryList.set(index, temp);
//
// index = parent;
//
// parent = index / 2;
//
// }
{
int parent = (index-1) / 2;
E bottom = entryList.get(index);
while( index > 0 &&
!entryList.get(parent).equals(bottom) )
{
bottom = entryList.get(parent); // move it down
index = parent;
parent = (parent-1) / 2;
} // end while
bottom = entryList.get(index) ;
} // end trickleUp()
}
// private void swap(int i, int j) {
// PriorityQueue<E, EntryType>.Entry tmp = entryList.get(i);
// entryList.set(i, entryList.get(j));
// entryList.set(j, tmp);
// }
private void trickleDown(int index){
int smallest = index;
if(getRightChildIndex(index) < index){
smallest = (getRightChildIndex(index));
}
if(getLeftChildIndex(index) < index){
smallest = getLeftChildIndex(index);
}
while (smallest != index){
trickleDown(smallest);
}
}
@Override
public int size() {
return entryList.size();
}
@Override
public boolean isEmpty() {
return entryList.isEmpty();
}
@Override
public void add(E element, int priority) {
if(isEmpty()) entryList.add(priority, element);
else{
entryList.add(priority, element);
bubbleUp(size());
}
//
// entryList.add((PriorityQueue<E, EntryType>.Entry) element);
// bubbleUp(entryList.size() - 1);
}
@Override
public E peek() throws NoSuchElementException {
if(isEmpty()) throw new NoSuchElementException();
else{
return entryList.get(size());
}
}
@Override
public E remove() {
// int result = (int) peek();
entryList.set(0, entryList.get(entryList.size() - 1));
// entryList.remove(entryList.size() - 1);
trickleDown(0);
return null;
}
public static void main(String args[]){
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(4);
a.add(6);
a.add(2);
a.add(5);
a.add(7);
a.add(9);
// System.out.println(a.size());
// System.out.println(a.isEmpty());
// System.out.println(a.get(size()).value);
System.out.println(a.peek());
System.out.println(a.toString());
// System.out.println(a.remove(5));
// System.out.println(a.toString());
}
}Ich weiß das ist alles noch sehr wirr und in der Entwicklungsphase, aber ich verstehe die genaue Herangehensweise nicht. Mir geht es vorsätzlich nur um die Methode peek() und das gesamte Konstrukt (die anderen Methode bitte nicht beachten, ist sowieso noch alles falsch). Ich möchte erst einmal verstehen, wie ich mit dieser ArrayList grundsätzlich arbeiten soll. wenn ich zum Beispiel den Befehl "System.out.println(a.peek());" ausführen möchte, funktioniert das nicht, weil "peek()" nicht für "ArrayList<Integer>" definiert worden ist. Und meine Frage ist, wie kann ich den nun die Methode "peek()" denn noch schreiben, um beispielsweise auf das erste oder auch letzte Element zuzugreifen, ohne den Rückgabewert zu verändern. Die einzelnen Methode sind mir auch noch durch das Interface gegeben worden. Hier das Interface:
Java:
import java.util.NoSuchElementException;
public interface PQInterface<E> {
/**
* @return the number of elements in the priority queue.
*/
public int size();
/**
* @return true if the priority queue contains no elements.
*/
public boolean isEmpty();
/**
* Adds element with given priority to the priority queue.
* Should have O(log n) runtime complexity.
*
* @param element
* @param priority
*/
public void add(E element, int priority);
/**
* Returns the element with the highest priority, but does not remove it.
* Should have O(1) runtime complexity.
*
* @return the element with the highest priority
* @throws NoSuchElementException if the queue is empty
*/
public E peek();
/**
* Removes the element with the highest priority and returns it.
* Should have O(log n) runtime complexity.
*
* @return the element with the highest priority
* @throws NoSuchElementException if the queue is empty
*/
public E remove();
}Das mag vielleicht jetzt alles auf einmal viel erscheinen, doch ich möchte nur zum Verständnis wissen, ob ich denn nun den Konstruktor ändern muss oder "private ArrayList<Entry> entryList;". Den Rest zu schreiben ist grundsätzlich nicht schwer und die Aufgabe an sich leicht, bloß ich verstehe nicht, wie ich das Grundgerüst schreiben soll, um überhaupt anfangen zu können. Danke im Voraus.
P.S.: Tut mir leid, dass es ein derart langer Post ist und sehr viel Informationen vorhanden sind, bloß ich poste lieber sehr viel Information rein, um vorläufige Fragen zu klären.
Zuletzt bearbeitet:
