Upload
amal-hellstern
View
120
Download
1
Embed Size (px)
Citation preview
EINI-IEINI-IEinführung in die Informatik Einführung in die Informatik für Naturwissenschaftler und für Naturwissenschaftler und
Ingenieure IIngenieure I
Kapitel 12
Claudio Moraga, Gisbert Dittrich
FBI Unido
2
Kap 12: HeapVorl “EINI-I"
1.2.2001
Gliederung Kapitel 12Gliederung Kapitel 12
• Zum Datentyp Heap– Beispiel eines Heaps– Eigenschaften eines Heaps– Definition des Heaps– Datentyp Heap– Zur Implementierung mittels eines Feldes
• Anwendungen– Heapsort– Prio-Warteschlangen, mit Heaps implementiert
3
Kap 12: HeapVorl “EINI-I"
1.2.2001
Beispiel: HeapBeispiel: Heap
3
6 12
7 13 18
9 10 21 13
14
20
Inhalt derKnoten1
2 3
4 5
8 9 10 11 12
6 7
Platznummerder Knoten
4
Kap 12: HeapVorl “EINI-I"
1.2.2001
Eigenschaften eines HeapsEigenschaften eines Heaps
• Ein Heap (Haufen) ist ein knotenmarkierter binärer Baum, so daß gilt:– (Die Markierungsmenge ist geordnet)
• im Beispiel: ganze Zahlen
– Der binäre Baum ist links-vollständig:• Alle Ebenen (vgl. Breitendurchlauf) sind vollständig besetzt
(bis evtl. auf die letzte); die letzte Ebene ist "von links voll aufgefüllt".
– Partiell angeordnete Markierungen:• Auf jedem Pfad von der Wurzel zu einem Blatt ist die Menge
der Knotenmarkierungen monoton steigend angeordnet.
5
Kap 12: HeapVorl “EINI-I"
1.2.2001
Definition: HeapDefinition: Heap
• Ein Heap (Haufen) ist ein knotenmarkierter binärer Baum, für den gilt:– Die Markierungsmenge ist geordnet.– Der binäre Baum ist links-vollständig.– Die Knotenmarkierung der Wurzel ist kleiner oder
gleich der Markierung des linken resp. rechten Sohnes (, sofern vorhanden).
– Die Unterbäume der Wurzel sind Heaps.
• --> An der Wurzel (Knoten 1) steht das kleinste/eines der kleinsten Element(e).
6
Kap 12: HeapVorl “EINI-I"
1.2.2001
Grobidee zum ADT Heap Grobidee zum ADT Heap
• Datenstruktur• Operationen
– Init– Einfügen eines Elementes in einen Heap– Entfernen eines der kleinsten Elemente/des
kleinsten Elementes aus dem Heap und Hinterlassen eines Rest-Heaps
– Zudem:• Heap ist leer ?/ Heap ist voll ?
• .....
7
Kap 12: HeapVorl “EINI-I"
1.2.2001
Implementierung über FeldImplementierung über Feld
6 23
4 7 18 26
17
17 6 23 4 7 18 26
1
2 3
4 5 6 7
1 2 3 4 5 6 7
Binärer Baum:
Feld:
Darstellung: Binärer Baum <--> Feld
8
Kap 12: HeapVorl “EINI-I"
1.2.2001
Implementierung über FeldImplementierung über Feld
• Beziehung: Baum- Feld-Darstellung :– Der Inhalt des i-ten Knotens in der Baumdarstellung
wird im i-ten Feldelement abgelegt.• Das bedeutet: Baum ebenenweise von links nach
rechts eintragen.
• Das Feldelement a[0] wird nicht verwendet!
• Lemma: – Die Söhne des Knotens i in einem Heap haben die
Knotennummern• 2i : linker Sohn • 2i + 1: rechter Sohn
• Beweis: Induktiv
9
Kap 12: HeapVorl “EINI-I"
1.2.2001
Implementierung über FeldImplementierung über Feld
• Ein Feld a mit n ganzen Zahlen realisiert einen Heap, falls a[i/2] < a[i] für alle i= 1, ...., n gilt.– Dabei ist "/" als ganzzahlige Division zu verstehen.
• z.B. 5/2 = 2
• In einem (Minimum-)Heap, realisiert durch das Feld a, steht das kleinste Element immer in a[1].
10
Kap 12: HeapVorl “EINI-I"
1.2.2001
Operation Einfügen: IdeeOperation Einfügen: Idee
Einfügen von 11 in unseren Heap
3
6 12
7 13 18
9 10 21 15
14
20neuer
Knoten11
Vergleich
18
11
Vergleich11
12
VergleichBeispiel:
11
Kap 12: HeapVorl “EINI-I"
1.2.2001
Operation Einfügen: AlgorithmusOperation Einfügen: Algorithmus
• Eingabe: – Heap a mit n Elementen, neues Element x
• Ergebnis: – Heap a mit n+1 Elementen, x seiner Größe gemäß
eingefügt
• Vorgehensweise:– Schaffe neuen Knoten n+1, setze a[n+1] = x
(Füge also neuen Knoten mit Beschriftung x in den Heap (evtl.noch an falscher Stelle) ein).
– Sortiere an richtige Stelle ein.
12
Kap 12: HeapVorl “EINI-I"
1.2.2001
Operation EinfügenOperation Einfügen
"An richtige Stelle einsortieren" - Idee:
einsortieren(k) :ist k=1, so ist nichts zu tun,ist k>1, so geschieht folgendes:
falls a[k/2] > a[k],vertausche a[k/2] mit a[k],rufe einsortieren(k/2) auf.
Hier istnämlich die
Heap-Bedingungverletzt.
Anmerkungen:
• k/2 ganzzahlige Division
• k = 0 wird ausgelassen !
13
Kap 12: HeapVorl “EINI-I"
1.2.2001
Operation EinfügenOperation Einfügen
void Heap::einsortieren(int Knoten_Nr) {if (Knoten_Nr > 1) { int DerVater_Nr = Knoten_Nr/2; if (HeapalsFeld[Knoten_Nr] <
HeapalsFeld[DerVater_Nr]) { Tausche(&HeapalsFeld[Knoten_Nr],
&HeapalsFeld[DerVater_Nr]);einsortieren(DerVater_Nr);}
}}
In das Feld HeapalsFeld wird richtig einsortiert gemäß:
14
Kap 12: HeapVorl “EINI-I"
1.2.2001
Operation EntfernenOperation Entfernen
• Idee einer Hau-Ruck-Lösung:– Entfernen des kleinsten Elements– Baue einen neuen Heap ohne das erste Element auf– (z.B. durch sukzessives Einfügen der Elemente in
einen neuen Heap.)
• Nachteil: – berücksichtigt nicht, daß vor dem Entfernen des
kleinsten Elements ein Heap vorliegt.
• Idee einer effizienteren Lösung:– Verwende genau diese Information
15
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT// JW: 3.2.2000 V1.0// Vorlage gemaess EED-Quelltext#include <iostream.h>#include <math.h> // für double pow (double d, int i)#include <limits.h> // fuer INT_MIN
const int maxKnoten = 70; const int unDef=INT_MIN; struct Heap { public:
void Init(); void Einfuegen(int);int Entfernen(); bool IstLeer();bool IstVoll();int Kopf(); void Druck();
private:int HeapalsFeld[maxKnoten + 1]; // Heap
´//beginnt mit Index 1, Index 0 wird nicht verwendet!int AnzahlKnoten; void einsortieren(int);void Tausche(int *, int *);
};
16
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Init() {AnzahlKnoten = 0;}
bool Heap::IstLeer() {return (AnzahlKnoten == 0 ? true : false);}
bool Heap::IstVoll() {return (AnzahlKnoten >= maxKnoten + 1 ?
true : false); // Heap beginnt mit Index 1!}
int Heap::Kopf() {return (IstLeer() ? unDef : HeapalsFeld[1]);}
17
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Tausche(int *a, int *b) {int temp = *a;
*a = *b;*b = temp;
}
void Heap::einsortieren(int Knoten_Nr) { if (Knoten_Nr > 1) {
int DerVater_Nr = Knoten_Nr/2;if (HeapalsFeld[Knoten_Nr] <
HeapalsFeld[DerVater_Nr]) { Tausche(&HeapalsFeld[Knoten_Nr],
&HeapalsFeld[DerVater_Nr]);einsortieren(DerVater_Nr);
}}
}
18
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Einfuegen(int Knotenmarkierung) {if (!IstVoll()) {
HeapalsFeld[++AnzahlKnoten] = Knotenmarkierung;
/* fuegen den Knoten ganz rechts in der letzten Ebene des Heaps ein*/einsortieren(AnzahlKnoten);
}}
19
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
int Heap::Entfernen() {/* Löschen eines Elementes durch Einfügen der Elemente 2-AnzahlKnoten in einen Hilfsheap und dann element-weises Einfügen des Hilfsheap in den "echten" Heap*/
int Anz=AnzahlKnoten; int HilfsHeapalsFeld[maxKnoten + 1];int BeschriftungWurzel;BeschriftungWurzel=HeapalsFeld[1];for (int i = 1; i < Anz; i++)
HilfsHeapalsFeld[i] = HeapalsFeld[i + 1];Init();
for (int i = 1; i < Anz; i++) Einfuegen(HilfsHeapalsFeld[i]);return BeschriftungWurzel;}
20
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Druck() { int n=1,x;
for (int i = 1; i <= AnzahlKnoten; i++) {
cout << HeapalsFeld[i] << " # ";x=(pow (2,n))-1;
// Ordnungszahl des letzten Knotens einer Ebeneif ((i%x)==0)
// letzter Knoten der Ebene n? { cout << endl; n++; // Neue Ebene beginnen }
}cout << "\n___________________" << endl;
}
21
Kap 12: HeapVorl “EINI-I"
1.2.2001
Wie erzeugt man dann einen Heap?Wie erzeugt man dann einen Heap?
Beobachtung:
jedes Blatt erfüllt die Heapbedingung
Allgemeinere Situation:
Wurzel erfülltdie Heap-Bedingung ?
Unterbäume mögendie Heap- Bedingung erfüllen
Vorgehen?
22
Kap 12: HeapVorl “EINI-I"
1.2.2001
Heap-ErzeugungHeap-Erzeugung
• Idee: Lasse „die Wurzel einsinken“:– Vergleiche den Eintrag im Knoten k mit denen seiner Söhne
(,soweit vorhanden)– Falls der Eintrag im Knoten k kleiner oder gleich als
diejenigen beider Söhne ist --> o.k.– Falls der Eintrag des Knotens k größer als der kleinere
Eintrag beider Söhne ist: • Ermittle den Sohn s mit dem kleineren Eintrag,• Vertausche den Eintrag des Knotens k mit demjenigen des
Sohnes s,• Wiederhole die Überlegungen mit diesem
Knoten s.
23
Kap 12: HeapVorl “EINI-I"
1.2.2001
BeispielBeispiel
3
8
10
9 10 15 13
12
18 14
20
Heap-Bedingungverletzt
Vergleich
Vergleich6
68ok
24
Kap 12: HeapVorl “EINI-I"
1.2.2001
Code zu "Erzeuge Heap", falls ... Code zu "Erzeuge Heap", falls ... void Heap::heapify(int Knoten_Nr) {
int LinkerSohn_Nr = 2*Knoten_Nr, RechterSohn_Nr = 2*Knoten_Nr + 1, selektierter_Sohn;if (LinkerSohn_Nr <= AnzahlKnoten
&& RechterSohn_Nr > AnzahlKnoten) // es gibt keinen rechten Sohn
{if (HeapalsFeld[LinkerSohn_Nr] < HeapalsFeld[Knoten_Nr])
Tausche(&HeapalsFeld[Knoten_Nr],&HeapalsFeld[LinkerSohn_Nr]); }
else if (RechterSohn_Nr <= AnzahlKnoten) { // es existieren linker und rechter Sohnselektierter_Sohn = (HeapalsFeld[LinkerSohn_Nr] < HeapalsFeld[RechterSohn_Nr] ? LinkerSohn_Nr : RechterSohn_Nr);
/* wähle den Sohn mit der kleineren Markierung aus. Bei Gleichheit wähleden rechten Sohn.*/
25
Kap 12: HeapVorl “EINI-I"
1.2.2001
Code zu "Erzeuge Heap", falls ...Code zu "Erzeuge Heap", falls ...
// Fortsetzung von void Heap::heapify
if (HeapalsFeld[selektierter_Sohn] < HeapalsFeld[Knoten_Nr])
// ist Heap-Bedingung verletzt?
{
Tausche(&HeapalsFeld[Knoten_Nr],
&HeapalsFeld[selektierter_Sohn]);
heapify(selektierter_Sohn);
}}}
26
Kap 12: HeapVorl “EINI-I"
1.2.2001
// 12_2_ADT_Heap: Heap als ADT// JW: 3.2.2000 V1.0// Vorlage gemaess EED-Quelltext//#include <iostream.h>#include <math.h> // für double pow (double d, int i)#include <limits.h> // fuer INT_MIN
const int maxKnoten = 70; const int unDef=INT_MIN; struct Heap { public:
void Init(); void Einfuegen(int);int Entfernen(); bool IstLeer();bool IstVoll();int Kopf(); void Druck();
private:int HeapalsFeld[maxKnoten + 1]; // Heap
// beginnt mit Index 1, Index 0 wird nicht verwendet!int AnzahlKnoten; void einsortieren(int);void Tausche(int *, int *); void heapify(int);};
27
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Init() {AnzahlKnoten = 0;}
bool Heap::IstLeer() {return (AnzahlKnoten == 0 ? true : false);}
bool Heap::IstVoll() {return (AnzahlKnoten >= maxKnoten + 1 ?
true : false); // Heap beginnt mit Index 1!}
int Heap::Kopf() {return (IstLeer() ? unDef : HeapalsFeld[1]);}
28
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Tausche(int *a, int *b) {int temp = *a;
*a = *b;*b = temp;
}
void Heap::einsortieren(int Knoten_Nr) { if (Knoten_Nr > 1) {
int DerVater_Nr = Knoten_Nr/2;if (HeapalsFeld[Knoten_Nr] <
HeapalsFeld[DerVater_Nr]) { Tausche(&HeapalsFeld[Knoten_Nr],
&HeapalsFeld[DerVater_Nr]);einsortieren(DerVater_Nr);
}}
}
29
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::Einfuegen(int Knotenmarkierung) {if (!IstVoll()) {
HeapalsFeld[++AnzahlKnoten] = Knotenmarkierung;
/* fuegen den Knoten ganz rechts in der letzten Ebene des Heaps ein*/einsortieren(AnzahlKnoten);
}}
int Heap::Entfernen() {int WurzelBeschriftung;WurzelBeschriftung = HeapalsFeld[1];HeapalsFeld[1] = HeapalsFeld[AnzahlKnoten--];heapify(1);return WurzelBeschriftung;}
30
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
void Heap::heapify(int Knoten_Nr) {int LinkerSohn_Nr = 2*Knoten_Nr,
RechterSohn_Nr = 2*Knoten_Nr + 1, selektierter_Sohn;
if (LinkerSohn_Nr <= AnzahlKnoten && RechterSohn_Nr > AnzahlKnoten) // es gibt keinen rechten Sohn
{if (HeapalsFeld[LinkerSohn_Nr] < HeapalsFeld[Knoten_Nr])
Tausche(&HeapalsFeld[Knoten_Nr], &HeapalsFeld[LinkerSohn_Nr]);
}
31
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung// Heapify Fortsetzung
else if (RechterSohn_Nr <= AnzahlKnoten) { // es existieren linker und rechter Sohn
selektierter_Sohn = (HeapalsFeld[LinkerSohn_Nr] <
HeapalsFeld[RechterSohn_Nr] ?LinkerSohn_Nr : RechterSohn_Nr);
/* wähle den Sohn mit der kleineren Markierung aus. Bei Gleichheit wähle den rechten Sohn.*/if (HeapalsFeld[selektierter_Sohn]
< HeapalsFeld[Knoten_Nr]) // ist Heap-Bedingung verletzt? { Tausche(&HeapalsFeld[Knoten_Nr],
&HeapalsFeld[selektierter_Sohn]); heapify(selektierter_Sohn);
}}}
32
Kap 12: HeapVorl “EINI-I"
1.2.2001
// Heap als ADT Fortsetzung
int zweierpotenz(int);void Heap::Druck() { int n=1,x;
for (int i = 1; i <= AnzahlKnoten; i++) {
cout << HeapalsFeld[i] << " # ";x = zweierpotenz(n) - 1;
// Ordnungszahl des letzten Knotens einer Ebeneif ((i%x)==0)
// letzter Knoten der Ebene n? { cout << endl; n++; // Neue Ebene beginnen }
}cout << "\n___________________" << endl;
}
33
Kap 12: HeapVorl “EINI-I"
1.2.2001
int zweierpotenz(int n){
int p;
for (p = 1; n>0; --n) p = p*2;
return p;
}
34
Kap 12: HeapVorl “EINI-I"
1.2.2001
Anmerkung zur HeapkonstruktionAnmerkung zur Heapkonstruktion
• heapify kann dazu herangezogen werden, aus einem Feld A mit n Elementen einen Heap zu konstruieren:– die Blätter sind bereits Heaps, – hat Knoten k also Blätter zu Söhnen, so erfüllen
seine Unterbäume die Heap-Bedingung,– durchlaufe die Knoten rückwärts von n/2 bis 1 und
rufe heapify für jeden Knoten auf,– für n >= j >= n/2 ist der Knoten j ein Blatt
35
Kap 12: HeapVorl “EINI-I"
1.2.2001
Implementierung des ADTs HeapImplementierung des ADTs Heap
const int maxKnoten = 70; ...
struct Heap {
public:
void Init(); void Einfuegen(int);
int Entfernen(); bool IstLeer();
bool IstVoll();int Kopf(); void Druck();
private:
int HeapalsFeld[maxKnoten + 1];
/* Heap beginnt mit Index 1,
Index 0 wird nicht verwendet! */
int AnzahlKnoten;
void einsortieren(int);
void Tausche(int *, int *);
void heapify(int);};
36
Kap 12: HeapVorl “EINI-I"
1.2.2001
Anwendung 1: HeapsortAnwendung 1: Heapsort
• Aufgabe: – Benutze Heap zum (effizienten) Sortieren.
• Heapsort arbeitet in zwei Phasen:– Aufbau eines Heaps aus einem Feld,– Schrittweiser Abbau des Heaps
• Auslesen des Wurzelelementes und Entfernen desselben
• Legen des "letzten" Elementes in die Wurzel
• Rekonstruktion der Heap-Bedingungfür diese restlichen Elemente.
37
Kap 12: HeapVorl “EINI-I"
1.2.2001
// 12_3_Heapsort.PPT#include <iostream.h>#include "12_2_ADT_Heap.cpp"main() { Heap * HeapfuerHeapsort = new Heap; int unsortierteFolge[10] = {9, 33, 2, 3, 14, 77,
4, 112, 6, 5}; int Wurzel; HeapfuerHeapsort->Init(); //(*HeapfuerHeapsort).Init( ) cout << "Heap aufbauen" << endl; for (int i=0; i < 10; i++) {
HeapfuerHeapsort-> Einfuegen(unsortierteFolge[i]);HeapfuerHeapsort->Druck();}
cout <<"\n\nund jetzt die sortierte Folge: "<< endl;while (!HeapfuerHeapsort->IstLeer()) {
Wurzel=HeapfuerHeapsort->Entfernen();cout << Wurzel << ", ";}
cout << endl;}
38
Kap 12: HeapVorl “EINI-I"
1.2.2001
Anwendung 2: PrioQueue mit HeapsAnwendung 2: PrioQueue mit Heaps
• Aufgabe: – Benutze Heap zum Implementieren einer
Prioritätswarteschlange.
39
Kap 12: HeapVorl “EINI-I"
1.2.2001
// 12_4_PQ_mit_Heap.PPT#include <iostream.h>#include "12_2_ADT_Heap.cpp"
Heap * PQ_Druck (Heap *); // Prototypen
// ImplementierungenHeap * PQ_Druck (Heap *Warteschlange){ int WurzelBeschriftung; Heap * Warteschlange2 = new Heap; Warteschlange2->Init(); while (!Warteschlange->IstLeer()) {
WurzelBeschriftung=Warteschlange->Entfernen();cout << WurzelBeschriftung << ", ";Warteschlange2->Einfuegen(WurzelBeschriftung);
}cout << endl;
return Warteschlange2;}
40
Kap 12: HeapVorl “EINI-I"
1.2.2001
// 12_4_PQ_mit_Heap.PPT - Fortsetzung
main() {Heap * Warteschlange = new Heap;int a[7] = {1, 1, 2, 3, 1, 4, 4};
Warteschlange->Init();for (int i=0; i < 7; i++) {
Warteschlange->Einfuegen(a[i]);Warteschlange=PQ_Druck(Warteschlange);}
cout << "\n\nund jetzt die Entfernung: " << endl;while (!Warteschlange->IstLeer()) {
Warteschlange->Entfernen();Warteschlange=PQ_Druck(Warteschlange);}
}
41
Kap 12: HeapVorl “EINI-I"
1.2.2001
Rückblick
binäre Suchbäume
Tiefendurchläufedurch einen
binären Baum
Breitendurchlaufdurch einen
binären Baum
Studium von Warteschlangen,
dabei Entdeckung vonADTs
ADT Prioritäts-Warteschlange
Studium von Heaps
Heapsort