[Belenus666]

Hy Leute,

ich brauch mal wieder eure Hilfe. Ich hab folgende Aufgabenstellung bekommen:

Wenn mit einem leeren Heap beginnend, nacheinander durch Verwendung der einfuege()- bzw. insert()-Methode, Elemente in den Heap eingefuegt werden, ist nach dem Einfuegen von n Elementen sicher gestellt, dass der Heap die Heap-Eigenschaften bezüglich der Anordnung der Elemente erfüllt. Diese Art bezeichnen wir als iterative Variante.
Betrachten Sie die folgende Alternative zur Herstellung der Heapeigenschaft, falls alle Werte von Anfang an in einem Feld vorliegen. Diese Art bezeichnen wir als geblockte Variante.
Implementieren Sie einen Heap, der int-Werte speichern kann und vergleichen Sie die Aufwände der beiden Alternativen zur Erstellung eines Heap, indem Sie in Ihrem Programm jeweils mitzählen wie viele Vertauschungen bei den beiden Alternativen ausgeführt werden. Für die Testläufe sollen nur Heaps verwendet werden, deren unterste Ebene voll gefüllt ist. Zum Einfuegen von n Zahlen verwenden Sie jeweils die Zahlen von 1 bis n in umgekehrter Reihenfolge, also z.B. 7, 6, 5, 4, 3, 2, 1.

Ich hab grade absolut keine Idee wie ich das umsetzen soll und bin für jede Anregung dankbar.

Grüße
Belenus

[Belenus666]

Nein Google ist nicht kaputt -.-

Es geht nicht um einen Heap-Sort sondern darum die Heap-Struktur herzustellen und nicht die Werte zu sortieren.
Was m.E.n. ein Unterschied ist und laut meiner Bücher und meines Professors auch.

Falls noch jmd. n konstruktiver Vorschlag hat und nicht mein nur einen auf wichtig tun zu müssen.

Wie gesagt ich bin dankbar für jeden Vorschlag...

[sirleo]

ernsthaft jetzt?

Du willst das wir dir bei deinen Hausaufgaben helfen?
Wenn du studierst ändere deine Fachrichtung, wenn du Schüler bist, wähl das Fach ab.

Ein HaldenSpeicher kenntzeichnet sich gerade dadurch aus das du die Sachen geordnet ablegst.
Wenn du danach die Halde"komprimierst"(hab Fachausdruck gerade nicht zur Hand) dann hast du wieder eine liste vorliegen, bzw, du kannst einen Haldenspeicher auch als Array implementieren.

Was auch immer du in der Vorlesung/Unterrichtsstunde gelehrt bekommen habt, nimm es dir nochmal zur Brust.
Programmierer/Entwickler/Informatiker zu sein bedeutet, einen grossteil der Zeit damit zuzubringen Sachen durchzulesen zu themen die schon jemand vor einem abgehandelt hat.
mfg

sirleo

[Belenus666]

@sirleo

Ernsthaft sonst hätte ich das nicht gepostet

Und nein ich will nicht das ihr meine "Hausaufgaben" löst ich hab lediglich nach nem Ansatz gefragt weil ich auf m schlauch stehe und aus meinen Unterlagen nicht schlau werde.

[sirleo]

OK, dann stell konkrete Fragen, dann kann man dir auch helfen.
Also was GENAU verstehst du nicht?

[Hamzty]

das is doch jetzt echt billig

[Belenus666]

So ich hab jetzt angefangen aber es funktioniert nicht.

Wäre nett wenn mal jmd drüber schauen kann.

public class Heap {

	static int count = 0;
	int[] Heap;
	static int n = count;

	public Heap(int maxlength) {
		Heap = new int[maxlength];
	}

	public void append(int value) {
		Heap[count] = value;
		count++;
		this.überführeInHeap(Heap);
	}

	// vertauscht in einem Array die Einträge mit Index x und y
	private static void vertausche(int[] a, int x, int y) {
		int z = a[x];
		a[x] = a[y];
		a[y] = z;
	}

	// versickert im Array mit Länge n das Element mit Index i
	private static void versickere(int[] a, int n, int i) {
		while (i <= n / 2) {
			int ln = 2 * i; // linker Nachfolger
			if (ln < n) // hat der Knoten einen rechten Nachfolger, und
			{
				if (a[ln + 1] > a[ln]) // ist der größer als der linke?
				{
					ln++; // dann benutze den rechten, sonst den linken
							// Nachfolger
				}
			}
			if (a[ln] > a[i]) {
				vertausche(a, i, ln); // vertausche mit größerem Nachfolger
				i = ln; // versickere weiter
			} else { // beide Nachfolger sind kleiner als das Element, kann
						// nicht
				i = n; // weiter versickern: Beende Schleife
			}
		}
	}

	// überführt ein Array in einen Heap
	public static void überführeInHeap(int[] a) {

		for (int i = n / 2; i >= 1; i--) { // starte von der Mitte aus rückwärts
			versickere(a, n, i);
		}
	}


	public void display() {
		for (int i = 0; i < count; i++) {
			System.out.print(Heap[i]);
		}
		System.out.println();
	}

}

Grüße
Belenus

[rabite]

Ich glaube, dass Du mit einem Array keine Heap-Struktur darstellen kannst.
Ich denke dass Du das ueber eine Sub-Klasse, die Du als Container benutzt realisieren sollst. Diese Klasse sollte also ein int und zwei Links zu den Nachfolgern enthalten (links und rechts).
Die Klasse Heap an der Du eigentlich schreibst enthaelt einen Link zur Wurzel und die Verwaltungsmethoden.

[sirleo]

Stimmt nicht kann man schon machen.
Je nachdem welchen Index das Wurzelelement hat sind die Linken bzw rechten Kinder
vom Knoten n 2n und 2n+1 bzw 2n+1 und 2n+2.

Also, bin nur drübergefolgen aber versickere ist glaube ich nicht ganz koscher.
eine Heapüberführung musst du auch über den ganzen Array machen.

Du hast keine Insertmethode für deinen Heap, nimm die und überführe Heap wird sau einfach.

Aber naja, meine Kristallkugel gibt nun mal nicht mehr her weil DU VERGESSEN HAST ZU SAGEN WAS GENAU NICHT STIMMT BZW WIE SICH DER FEHLER ÄUSSERT.
wie soll man dir genau helfen?

mfg

sirleo

[rabite]

Natuerlich ist es moeglich das in der Art zu loesen, aber er hat ja gesagt, dass es darum geht eine Heap-Struktur herzustellen - das interpretiere ich eher so wie ich es gesagt habe
ich faende es so auch irgendwie einfacher