Prioritätswarteschlangen: Difference between revisions
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht: | Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht: | ||
[[Image:heapArray.png | [[Image:heapArray.png|400px]] | ||
==Sortieren als Suchproblem== | |||
Systematisches Fragen mit True und False kann auch als Baum dargestellt werden.<br> [[Image:penka.png|400px]] | |||
Hier ein Beispiel.Als Eingabe sind drei Zahlen angegeben a={1,2,3},wobei die Reihenfolge nicht bekannt ist.<br>[[Image:trueFalseBeisp.png|700px]]<br> Also mit Eingabe von drei Elemnten müssen im ungünstigsten Fall drei Schritte vorgenommen werden.<br>Die allgemeine Regel lautet: es gibt N mögliche Lösungen <br> =>der Baum muss N Blätter haben<br> =>ein baum mit N Blättern hat mindestens die Höhe logN<br>[[Image:vollbaum.png|left]] | |||
| Line 17: | Line 20: | ||
vollständiger Baum (oder balancierter Baum)[http://hci.iwr.uni-heidelberg.de/alda/index.php/Suchen#Balance_eines_Suchbaumes]<br>2^d+1 Knoten<br>2^d Blätter<br> | |||
| Line 30: | Line 34: | ||
==Sortieren== | |||
N = n!wenn das Arrey n Elemente hat<br>Zum Beispiel: 3! = 1*2*3 = 6 <br> log6 <math>\approx</math> 2,6 => d = 3 - bei dem Frage-Baum brauch man im ungünstigsten Fall drei Schritte (True/False)<br>log6 <math>\approx</math> 2,6 - weil nicht jeder Pfad zu Ende durchgelaufen sein soll, um die Lösung zu bekommen.<br>d<math>\ge</math>log<math>_2</math>n! = log<math>_2</math>(1,2...n) = log<math>_2</math>1 + log<math>_2</math>2 + ... + log<math>_2</math>n = <math>\sum_{n=1}^n log_2n | |||
</math><br> | |||
===Abschätzung von Summen durch Integrale=== | |||
gegeben : f(x) - monoton wachsend <br> [[Image:integralGraph.png|400px|left]]<br> | |||
<math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lfloor x \big\rfloor)dx</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(x)dx | |||
</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lceil x \big\rceil)dx</math> <br> | |||
<math>\downarrow</math> | |||
<math>\textstyle \int\limits_{x_1}^{x_1 + 1} \underline{f(x_1)}dx</math> + ...+ <math>\textstyle \int\limits_{x_2-1}^{x_2} f(x_2 - 1)dx | |||
</math> = <math>\sum_{k=x_1}^{x_2-1} f(k)</math><br> ( angenommen <math>x_1</math> und <math>x_2</math> <math>\in </math> <math>\mathbb{N},\mathbb{Z}</math> | |||
)<br> | |||
wobei f(<math>x_1</math>) = f(<math>\big\lfloor x \big\rfloor </math><math>)_{x_1}^{x_1 +1}</math><br> | |||
<math>\textstyle \int\limits_{x_1}^{x_1 +1} f(x_1)dx</math> = f(<math>x_1</math>) <math>\textstyle \int\limits_{x_1}^{x_1 + 1} 1dx</math> = f(<math>x_1</math>)x<math>\textstyle \int\limits_{x_1}^{x_1 + 1}</math> = f(x_1) | |||
Revision as of 14:08, 1 June 2008
Prioritätswarteschlangen
Heap
- Datenstruktur optimiert für Prioritätssuche
- Def: ein linkslastiger Binärbaum ist ein Baum mit <math>d(node.left) \geq d(node.right)</math>
Ein Heap ist ein linkslastiger, perfekt balancierter Baum.
Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht:
Sortieren als Suchproblem
Systematisches Fragen mit True und False kann auch als Baum dargestellt werden.
Hier ein Beispiel.Als Eingabe sind drei Zahlen angegeben a={1,2,3},wobei die Reihenfolge nicht bekannt ist.
Also mit Eingabe von drei Elemnten müssen im ungünstigsten Fall drei Schritte vorgenommen werden.
Die allgemeine Regel lautet: es gibt N mögliche Lösungen
=>der Baum muss N Blätter haben
=>ein baum mit N Blättern hat mindestens die Höhe logN
vollständiger Baum (oder balancierter Baum)[1]
2^d+1 Knoten
2^d Blätter
Sortieren
N = n!wenn das Arrey n Elemente hat
Zum Beispiel: 3! = 1*2*3 = 6
log6 <math>\approx</math> 2,6 => d = 3 - bei dem Frage-Baum brauch man im ungünstigsten Fall drei Schritte (True/False)
log6 <math>\approx</math> 2,6 - weil nicht jeder Pfad zu Ende durchgelaufen sein soll, um die Lösung zu bekommen.
d<math>\ge</math>log<math>_2</math>n! = log<math>_2</math>(1,2...n) = log<math>_2</math>1 + log<math>_2</math>2 + ... + log<math>_2</math>n = <math>\sum_{n=1}^n log_2n
</math>
Abschätzung von Summen durch Integrale
gegeben : f(x) - monoton wachsend
<math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lfloor x \big\rfloor)dx</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(x)dx
</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lceil x \big\rceil)dx</math>
<math>\downarrow</math>
<math>\textstyle \int\limits_{x_1}^{x_1 + 1} \underline{f(x_1)}dx</math> + ...+ <math>\textstyle \int\limits_{x_2-1}^{x_2} f(x_2 - 1)dx
</math> = <math>\sum_{k=x_1}^{x_2-1} f(k)</math>
( angenommen <math>x_1</math> und <math>x_2</math> <math>\in </math> <math>\mathbb{N},\mathbb{Z}</math>
)
wobei f(<math>x_1</math>) = f(<math>\big\lfloor x \big\rfloor </math><math>)_{x_1}^{x_1 +1}</math>
<math>\textstyle \int\limits_{x_1}^{x_1 +1} f(x_1)dx</math> = f(<math>x_1</math>) <math>\textstyle \int\limits_{x_1}^{x_1 + 1} 1dx</math> = f(<math>x_1</math>)x<math>\textstyle \int\limits_{x_1}^{x_1 + 1}</math> = f(x_1)
