was ist heap eingebettet in array

mstrkrft_

Hallo,

wir sollen einen Heapsort Algorithmus programmieren. dazu gehen wir Schrittweise vor. Allerdings verstehe ich nicht, was ein Heap eingebettet in einem Array sein soll. Hier die Aufgabenstellung:

Schreiben Sie eine Funktion, die den Index des linken Sohns für einen gegebenen
Vater in Heap-im-Array berechnet! Überlegen Sie wie man den Index des rechten
Sohns berechnen kann.Der Heap-Im-Array ist eine linksvollständiger Heap!

Heißt das Quasi ich habe einen Baum
...........1
......2..........3
...55....44
(das soll einen Baum darstellen ^^)
und denn dann quasi in ein Array geschrieben:1,2,3,55,44

pointercrash**

Heya,

das hat mit dem C- Heap erstmal nichts zu tun, sondern mit dem Heapsort- Algorithmus. Lies das doch erstmal durch und versuch Dich unter C dran - that's Your job.

mstrkrft_

hey, ja da war ich auch schon :). Das Problem ist nur, dass wir halt die Teilaufgaben abarbeiten müssen und das sind nunmal diese Formulierungen.

habe die aufgabe glaube ich auch schon gelöst, ist ja recht einfach:

unsigned int IndexOfLeftSon(unsigned int nIndexOfFather){

	unsigned int nIndexOfLeftSon = nIndexOfFather*2+1;

	return nIndexOfLeftSon;
}

Allerdings kann ich mir noch nicht so wirklich etwas darunter vorstellen wie das bei uns in den Teilaufgaben formuliert ist.

Hallo,

mstrkrft_ schrieb:

...Allerdings verstehe ich nicht, was ein Heap eingebettet in einem Array sein soll...

Das ist hier unter 4.2 anschaulich dargestellt:
http://www.linux-related.de/index.html?/coding/sort/sort_heap.htm

Gruß,
B.B.