Prioritätswarteschlangen

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 $\approx$ 2,6 => d = 3 - bei dem Frage-Baum brauch man im ungünstigsten Fall drei Schritte (True/False)
log6 $\approx$ 2,6 - weil nicht jeder Pfad zu Ende durchgelaufen sein soll, um die Lösung zu bekommen.
d$\geq$log$_{2}$n! = log$_{2}$(1,2...n) = log$_{2}$1 + log$_{2}$2 + ... + log$_{2}$n = $\sum _{n=1}^{n}log_{2}n$

Abschätzung von Summen durch Integrale

gegeben : f(x) - monoton wachsend

$\textstyle \int \limits _{x_{1}}^{x_{2}}f({\big \lfloor }x{\big \rfloor })dx$ $\leq$ $\textstyle \int \limits _{x_{1}}^{x_{2}}f(x)dx$ $\leq$ $\textstyle \int \limits _{x_{1}}^{x_{2}}f({\big \lceil }x{\big \rceil })dx$

$\downarrow$

$\textstyle \int \limits _{x_{1}}^{x_{1}+1}{\underline {f(x_{1})}}dx$ + ...+ $\textstyle \int \limits _{x_{2}-1}^{x_{2}}f(x_{2}-1)dx$ = $\sum _{k=x_{1}}^{x_{2}-1}f(k)$
( angenommen $x_{1}$ und $x_{2}$ $\in$ $\mathbb {N} ,\mathbb {Z}$ )

wobei f($x_{1}$) = f(${\big \lfloor }x{\big \rfloor }$$)_{x_{1}}^{x_{1}+1}$

$\textstyle \int \limits _{x_{1}}^{x_{1}+1}f(x_{1})dx$ = f($x_{1}$) $\textstyle \int \limits _{x_{1}}^{x_{1}+1}1dx$ = f($x_{1}$)x$\textstyle \int \limits _{x_{1}}^{x_{1}+1}$ = f(x_1)

$\sum _{k=x_{1}}^{x_{2}-1}f(k)\leq \textstyle \int \limits _{x_{1}}^{x_{2}}f(x)dx$

$\sum _{k=x_{1}+1}^{x_{2}}f(k)\geq \textstyle \int \limits _{x_{1}}^{x_{2}}f(x)dx\iff$ $\sum _{k=x_{1}}^{x_{2}}f(x)\geq \textstyle \int \limits _{x_{1}-1}^{x_{2}}f(x)dx$

für uns gilt: f(x) = log$_{2}$(x)

log$_{2}$1 + $\sum _{k=2}^{n}log_{2}x\geq \textstyle \int \limits _{1}^{n}log_{2}(x)dx$ = ${\frac {1}{ln2}}\textstyle \int \limits _{1}^{n}log(x)dx$ = ${\frac {1}{ln2}}$ [xlogx - x]$_{x=1}^{n}$ = nlog$_{2}$(n) - ${\frac {n-1}{ln2}}$ = $\Omega$(nlog$_{2}$n)

$\Rightarrow$ d = log$_{2}$n! = $\Omega$(nlogn)

kein Sortieralgorithmus auf Basis paarweise Vergleiche ist asymthotisch schneller als Mergesort

Prioritätswarteschlangen

* Max Priority Quene : insert(x)
                      x = largest()
                      removeLargest()

* Min Priority Quene: smallest()
                     removeSmallets()

Prioritätswarteschlange als Suchproblem

• Sequentielle Suche - Array mit Prioritäten : insert(x)<=> a.append(x) ( ${\mathcal {O}}(1)$(amortisierte Komplexität))

def largest(a):

   if len (a) == 0:  

       raise RuntimeError("...")

    max = a[0]

    k = 0

    for n in range(1, len(a):             (innere Schleife von SelectionSort)

       if a[n] > max                       (Das ganze hat die Komplexität: N = len(a) => ${\mathcal {O}}(N)$

           max = a[n]

               k = n

    return k

Bei kleine Array ist dies die schnellste Methode

Binärer (balancierter)Suchbaum

insert => z.B. wie beim Anderson Baum [2] ${\mathcal {O}}(logN)$

def largest(node):                     # Wurzel

   if node.right is not None:    #rechts stehen immer  die großen

       return largest(node.right)

   return node                   #wenn es nicht mehr nach rechts geht, dann haben wir den größten Knoten gefunden

Das ganze hat ${\mathcal {O}}(logN)$ Komplexität
Ergebnis: gute Komplexität aber komplizierte Datenstruktur

Heap

• Datenstruktur optimiert für Prioritätssuche - man sucht nicht effizient alle Knoten, sondern nur einen bestimmten z.B. Heap max
  
• Definition: ein linkslastiger Binärbaum ist ein Baum mit $d(node.left)\geq d(node.right)$

Ein Heap ist ein linkslastiger, perfekt balancierter Baum. (lässt sich max. um 1 unterscheiden)

Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht:

index[parent] = [(indexChild - 1)/2]   #[] heißt abgerundet

index[left] = index[parent]2 + 1

index[right] = index[parent]2 + 2

=> linkslastiger perfect balancierter Binärbaum kann effizient als Array abgespeichert werden
=>verwende Indizes wie oben

Heap - Bedingung

• die Wurzel hat höhere Prioriät als die Kinder(gilt für jeden Teilbaum)
  

=>Wurzel = array[0] hat die größte Priorität

def largest(h):

    return h[0]        ${\mathcal {O}}(N)$

Einfügen in einem Heap

h - Array #speichrt Haep

 def insert(h,x):

     h.append(x)  # wir speichern den Wurzel am Ende, so wird glecih zu einem linkslastigen perfect balancierten Baum (die Haep - Bedingung ist erfüllt)

     upheap(h, len(h) - 1):

def upheap(h, k):

   """k-tes Element evtl. an der falsche Stelle

   """

   v = h[k]

   while True      #endlose Schleife
        
       if k == 0:

           break

       parent = (k - 1)/2

       if h[parent]>v:

           break

       h[k] = h.parent

       k = parent

       h[k] = v

def removeLargest(h):
    h[0] = h[len(h) - 1]

    del h[len(n) - 1]              ${\mathcal {O}}(1)$

    downHeap(h, 0)                       ${\mathcal {O}}(logN)$

def downHeap(h, k):

    v = h[k]

    while True

        child = 2k + 1              #linke Kind

        if child $\geq$len{h):

              break

        if child < and h[child] < h[child + 1]         #rechtes Kind

              child = child + 1
        if v $\geq$ h[child]:

              break

        h[k] = h[child]

        k = child

   h[k] = v