algodat-ue4.md 20 KB
% AlgoDat ue4 % 12 Mai 2020
Aufgabe 1
Es wird jeweils
$$ [17, 16, 11, 9, 20, 0, 3] $$
eingefügt. Weiters gilt $m = 7$.
a
Disclosure
Die Ergebnisse wurden wie folgt berechnet:
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> [n % 7 for n in numbers]
[3, 2, 4, 2, 6, 0, 3]
$$ h(k) = k \mod m $$
$K_i$ bezeichne die Ketten der einzelnen Indizes zu Schritt $i$
| Index | $K_1$ | $K_2$ | $K_3$ | $K_4$ | $K_5$ | $K_6$ | $K_7$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | |||||
| 1 | leer | ||||||
| 2 | 16 | 16 | 16 $\to$ 9 | 16 $\to$ 9 | 16 $\to$ 9 | 16 $\to$ 9 | |
| 3 | 17 | 17 | 17 | 17 | 17 | 17 | 17 $\to$ 3 |
| 4 | 11 | 11 | 11 | 11 | 11 | ||
| 5 | leer | ||||||
| 6 | 20 | 20 | 20 |
Beim Einfügen von 9 gibt es eine Kollision mit 16, da $h(16) = h(9) = 2$. In diesem Fall wird 9 einfach an die entsprechende Kette angehängt.
Beim Suchen von 9 wird die Kette an Index 2 hergenommen, da $h(9) = 2$, welche dann bis zum Ende linear durchsucht wird, um schließlich das Ergebnis zurückzuliefern.
Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{9}{7} = 1.29$.
| k | 17 | 16 | 11 | 9 | 20 | 0 | 3 | Summe | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| find(k) | 1 | + | 1 | + | 1 | + | 2 | + | 1 | + | 1 | + | 2 | = | 9 |
b
Disclosure
Die Ergebnisse wurden wie folgt berechnet:
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> import math
>>> def h(k):
... return math.floor(7 * (k * math.sqrt(2) - math.floor(k * math.sqrt(2))))
>>> def hash(k, i):
... return (h(k) + 1/2 * i + 1/2 * i * i) % 7
>>> [(n, int(hash(n, 0))) for n in numbers]
[(17, 0), (16, 4), (11, 3), (9, 5), (20, 1), (0, 0), (3, 1)]
>>> [(n, int(hash(n, 1))) for n in numbers]
[(17, 1), (16, 5), (11, 4), (9, 6), (20, 2), (0, 1), (3, 2)]
>>> [(n, int(hash(n, 2))) for n in numbers]
[(17, 3), (16, 0), (11, 6), (9, 1), (20, 4), (0, 3), (3, 4)]
>>> [(n, int(hash(n, 3))) for n in numbers]
[(17, 6), (16, 3), (11, 2), (9, 4), (20, 0), (0, 6), (3, 0)]
$$ h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m, c_1 = \frac{1}{2}, c_2 = \frac{1}{2} $$ $$ h'(k) = \lfloor m (k A - \lfloor k A \rfloor) \rfloor, A = \sqrt{2} $$
| Index | $T_1$ | $T_2$ | $T_3$ | $T_4$ | $T_5$ | $T_6$ | $T_7$ |
|---|---|---|---|---|---|---|---|
| 0 | 17 | 17 | 17 | 17 | 17 | 17 | 17 |
| 1 | 20 | 20 | 20 | ||||
| 2 | 3 | ||||||
| 3 | 11 | 11 | 11 | 11 | 11 | ||
| 4 | 16 | 16 | 16 | 16 | 16 | 16 | |
| 5 | 9 | 9 | 9 | 9 | |||
| 6 | 0 | 0 |
Die Reihenfolge in der Indizes berechnet werden, wobei bei Kollisionen die Funktion $h(k, i)$ mit jeweils inkrementiertem Wert $i$ noch einmal aufgerufen wird, ist wie folgt:
$h(17, 0) = 0 \longrightarrow h(16, 0) = 4 \longrightarrow h(11, 0) = 3 \longrightarrow h(9, 0) = 5 \longrightarrow h(20, 0) = 1 \longrightarrow h(0, 0) = h(17, 0) = 0 \longrightarrow h(0, 1) = 1 \longrightarrow h(0, 2) = 3 \longrightarrow h(0, 3) = 6 \longrightarrow h(3, 0) = 1$, $h(3, 1) = 2$
Beim Suchen von 9 wird ergibt sich durch $h(9, 0) = 5$ der Index 5.
Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{11}{7} = 1.57$.
| k | 17 | 16 | 11 | 9 | 20 | 0 | 3 | Summe | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| find(k) | 1 | + | 1 | + | 1 | + | 1 | + | 1 | + | 4 | + | 2 | = | 11 |
c
Disclosure
Die Ergebnisse wurden wie folgt berechnet:
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> def h_1(k):
... return k % 7
>>> def h_2(k):
... return (k % 5) + 1
>>> def hash(k, i):
... return (h_1(k) + (i * h_2(k))) % 7
>>> [hash(n, 0) for n in numbers]
[3, 2, 4, 2, 6, 0, 3]
>>> [hash(n, 1) for n in numbers]
[6, 4, 6, 0, 0, 1, 0]
>>> [hash(n, 2) for n in numbers]
[2, 6, 1, 5, 1, 2, 4]
>>> [hash(n, 3) for n in numbers]
[5, 1, 3, 3, 2, 3, 1]
>>> [hash(n, 4) for n in numbers]
[1, 3, 5, 1, 3, 4, 5]
$$ h(k, i) = (h_1(k) + i h_2(k)) \mod m $$ $$ h_1(k) = k \mod m $$ $$ h_2(k) = (k \mod 5) + 1 $$
| Index | $T_1$ | $T_2$ | $T_3$ | $T_4$ | $T_5$ | $T_6$ | $T_7$ |
|---|---|---|---|---|---|---|---|
| 0 | 9 | 9 | 9 | 9 | |||
| 1 | 0 | 0 | |||||
| 2 | 16 | 16 | 16 | 16 | 16 | 16 | |
| 3 | 17 | 17 | 17 | 17 | 17 | 17 | 17 |
| 4 | 11 | 11 | 11 | 11 | 11 | ||
| 5 | 3 | ||||||
| 6 | 20 | 20 | 20 |
Hier verläuft treten keine Kollisionen bis zum Schlüssel 9. Der Index für Schlüssel 9 ergibt sich dann durch $h(9, 1) = 0$. Weiters kollidiert 0, wo schließlich sich ein Index ergibt durch $h(0, 1) = 1$. Zuletzt kollidiert 3, mehrere Male sogar, wo sich schließlich ein Index ergibt durch $h(3, 4) = 5$.
Bei einer Suche nach 9 überprüfen wir zunächst Index 2, da $h(9, 0) = 2$. Weil dies unerfolgreich verläuft, überprüfen wir zunächst Index 0, da $h(9, 1) = 0$. An dieser Stelle wird 9 erfolgreich gefunden.
Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{13}{7} = 1.86$.
| k | 17 | 16 | 11 | 9 | 20 | 0 | 3 | Summe | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| find(k) | 1 | + | 1 | + | 1 | + | 2 | + | 1 | + | 2 | + | 5 | = | 13 |
Aufgabe 2
a
Die alte Implementierung (I) ist folgende:
public int hashCode() {
int hash = 0;
int skip = Math.max(1, length() / 8);
for (int i = 0; i < length(); i += skip)
hash = (hash * 37) + charAt(i);
return hash;
}
Die neue Implementierung (II) ist folgende:
public int hashCode() {
int hash = 0;
for (int i = 0; i < length(); i++)
hash = (hash * 31) + charAt(i);
return hash;
}
Es gibt zwei hauptsächliche Unterschiede. Zum einen ist die Konstante von 37 auf 31 geändert worden, aber das spielt für uns keine Rolle, weil beide Primzahlen sind. Der nächste Unterschied ist, dass kein skip mehr berechnet wird. Damit ändert sich die Zahl der Durchläufe, die sich so vergleichen lässt:
I) Durchläufe $dI$: $1 \leq d \leq length() / 8$ II) Durchläufe $d{II}$: $1 \leq d \leq length()$
Es fällt natürlich auf, dass durch skip einfach Teile des Strings übersprungen werden. Dadurch lässt sich besonders leicht ein Beispiel für eine Kollision konstruieren:
strlst@ayaya ~ calc 24 / 8
3
strlst@ayaya ~ echo -n abcdefghijklmnopqrstuvwx | wc -c
24
strlst@ayaya ~ echo -n a11d11g11j11m11p11s11v11 | wc -c
24
Die Kollision lässt sich auch so verbildlichen:
012 012 012 012 012 012 012 012
abc def ghi jkl mno pqr stu vwx
a11 d11 g11 j11 m11 p11 s11 v11
Es wird durch skip nur jeder 3 Buchstabe (also unter einer Spalte mit "0") miteinbezogen. Für längere Strings ist die Menge an kollidierenden Zeichenfolgen sehr schnell sehr groß. Die neue Implementierung berücksichtigt alle Zeichen eines Strings.
Die Laufzeit beider Varianten unterscheidet sich um einen konstanten Faktor, nämlich 8, ist daher asymptotisch gleich performant.
b
Die bessere Wahl ist jene, die weniger Kollisionen verursacht, also die ersten vier Zeichen. Da vorallem bei diesem Beispiel alle Studierenden beim selben E-Mail Provider sind, gibt es wenig bis gar keine Variation bei den letzten vier Zeichen und die Kollisionen werden zahlreich!
vorschlag: die meisten informationen mit einbeziehen Ein Vorschlag wäre, zu versuchen die größtmögliche variierenden Stellen miteinzubeziehen. Vorallem da bei Studierenden der erste Buchstabe immer gleich ist, wäre es naheliegend, die letzten vier Stellen des Teils der E-Mail Adresse vor dem "@" miteinzubeziehen.
Ein Beispiel soll das illustrieren:
....
zufälligemail@addresse.com
^^^^
c
Angenommen unsere Hashfunktion nimmt ganzzahlige Zahlen $x \in \mathbb{N}$, dann lässt sich folgendes sagen:
$$ \forall x \in \mathbb{N} \forall n \in [0, m) : P(h(x) = n) = \frac{1}{m} $$
D.h., für arbiträre Eingaben $x$ ist die Wahrscheinlichkeit, als Ergebnis der Hashfunktion $h(k)$ genau $n$ zu bekommen, $1/m$, und das für alle $n$ zu diesen $x$.
Weiters definieren wir folgende Kenngröße, welche uns angibt, wie voll bereits die Hashtabelle ist:
$\alpha$ = k/m ... load factor, wobei $k$ die Anzahl der gerade gespeicherten Elemente ist, $k \leq m$
Die Laufzeit lässt sich eingrenzen durch eine worst-case und best-case Analyse. Da im best-case immer das entsprechende Element sofort gefunden wird (auch bei voller Hashtabelle), können wir eine best-case Laufzeitkomplexität von $O(1)$ observieren. Da im worst-case immer alle Elemente durchsucht werden, und die Hashtabelle höchstens $m$ Elemente besitzt, wobei gilt $n \in [0, m)$, können wir eine worst-case Laufzeitkomplexität von $O(n)$ erwarten.
Abhängig wie viele Elemente durchschnittlich pro Index $n$ belegt sind, varriert die Performance. $\alpha$ als Kenngröße sagt uns, wie lang durchschnittlich eine Kette ist. Für jeweils unerfolgreiche Suche, sowie erfolgreiche Suche nach einem beliebigen Element, erwarten wir also $\alpha$ Elemente durchgehen zu müssen (leider entgeht hier das entsprechende Werkzeug, um einen statistisch korrekten Beweis zu führen). Wenn wir auch noch den Fall $k = 0$ berücksichtigen, dann können wir sagen, die average-case Laufzeitkomplexität fällt auf $O(\alpha + 1)$.
Aufgabe 3
a
In diesem Beispiel besteht die Hash Tabelle aus 3 möglichen Indizes, $m = 3$. Die Hashfunktion nimmt jeweils den ersten Buchstaben eines Strings und mapped diese auf die Indizes der Hashtabelle.
A:
B:
C:
$$ h(name) = upper(name[0]) $$
Wenn wir jetzt zwei Datensätze einfügen:
insert(alpha)
insert(aleph)
entsteht folgende Tabelle:
A: alpha
B: aleph
C:
Durch löschen von dem ersteren Datensatz:
delete(alpha)
entsteht dann folgende Tabelle:
A:
B: aleph
C:
Problematisch ist nun eine Suche nach dem zweiten Datensatz, find(aleph) hört nämlich gleich zu Beginn der Suche auf, obwohl aleph enthalten ist!
b
$$ h(k) = k \mod m, m = 7 $$
0:
1:
2:
3:
4:
5:
6:
Wir fügen nun der Reihe nach die Elemente 1, 2, 8, 15 und 9 ein. Die Hashtabelle sieht dann wie folgt aus:
0:
1: 1
2: 2
3: 8
4: 15
5: 9
6:
Wenn wir jetzt nach dem Schema das Element 1 löschen, werden wir wegen $h(1) = 1$ das Element an Index $i = 1$ entfernen. Wir suchen nun ein kleinstmögliches $j$, sodass $T[(i + j + 1) \mod m] = leer$ und $T[(i + j + 1) \mod m] \neq leer$. Diese zwei Stellen finden sich an Indizes 5 und 6, sodass $j = 4$. Wenn wir jetzt einfach das Element an Index $(i + j) = 5$ verschieben an Index $i = 1$, dann kann zwar jedes Element für das gilt $h(k) = 1$ immer noch gefunden werden, aber nicht zwingend jedes Element für das gilt $h(k) = 2$. Inzwischen sieht unsere Tabelle wie folgt aus:
0:
1: 9
2: 2
3: 8
4: 15
5:
6:
Eine Suche nach 9 würde nur dann funktionieren, wenn die Hashtabelle von Index 2 beginnend bis Index 1 vollständig gefüllt ist (wobei an der Grenze 6 wieder bei 0 angefangen wird zu zählen)! Weil dies nicht der Fall ist und die Suche bei Index 4 bereits abbricht, kann 9 nicht gefunden werden, obwohl dieses enthalten ist.
c
Man könnte den zu löschenden Eintrag entfernen und die gesamte Hashtabelle rekonstruieren. Natürlich ist das mit einer sehr ungünstigen Laufzeit von $\Omega(n)$ für jede Löschoperation verbunden.
Eine klügere Variante wäre es, zu versuchen, den Zustand vor einfügen des zu löschenden Eintrags wiederherzustellen. Dabei beginnen wir bei $i$, an wessen Stelle wir das Element löschen. Nun iterieren wir von dieser Stelle aus die restliche Liste. In jedem Schritt speichern wir uns unter last den Eintrag den wir eben betrachten, wenn folgendes gilt:
- $h(T[i]) = i$
D.h., die Hashfunktion liefert uns für das Element das wir gerade betrachten Index $i$. Das bedeutet, dass dieses Element ursprünglich dafür vorgesehen war, an Stelle $i$ platziert zu werden, aber es durch eine Kollision weiterversetzt wurde. Wir hören auf zu iterieren, sobald folgendes eintritt:
- $T[i]$ ist ein (tatsächlich) freier Eintrag
last sollte nun das letzte Element der Hashtabelle beinhalten, welches an die Stelle $i$ an der wir gelöscht haben eingefügt worden wäre. Aber wir müssen vorsichtig sein, wir müssen nachdem wir last nach $i$ verschoben haben, dasselbe noch einmal durchführen, diesmal mit dem Index von last, damit wir die Suche nach Elementen für jene die Hashfunktion andere Indizes berechnet nicht zerstören.
Aufgabe 4
a
Bloom Filter besitzen eine ähnliche Charakteristiken zu Hash Tabellen, nämlich unterstützt ein Bloom Filter äußerst performante Operationen für Suche und Einfügen. Während aber bei Hashtabellen normalerweise das Element selbst gespeichert wird und diese Daten abrufbar sein sollen, geht es bei Bloom Filter nur um die Existenz von Elementen. Das ergibt eine außerordentliche Platzeffizienz. Eine beispielhafte Anwendung in einer praktischen Datenstruktur wäre HashSet, wobei aber auf eine Eigenschaft Acht zu nehmen ist.
Bloom Filter können false positives haben. D.h., ein Element, dass nie eingefügt wurde, könnte dennoch gefunden werden. Umgekehrt aber gibt es keine false negatives, es kann nie etwas nicht gefunden werden, was schon eingefügt wurde.
Löschen ist eine komplizierte Angelegenheit, und viele Variationen unterstützen diese Operation gar nicht.
Allgemein kann ein Bloom Filter als Funktion definiert werden, welche auf beliebige Eingangsdaten $M$ operieren und im Hintergrund ein $m$ bit langes Datenwort speichern. Dabei sind sind Einfügen und Suchen dann folgende Funktionen:
$$ B_{insert} : M \to W, W = (w_0, w1, ..., w{m - 1}) $$
$$ B_{find} : M \to { true, false } $$
Dabei basiert dieses abbilden auf mehrere Hashfunktionen, in unserem Fall die Menge an Hashfunktionen $H = { h_1, h_2, ..., h_k }$.
Pseudo Code würde für diese Funktionen wie folgt aussehen:
x ... Eingangsdaten, $x \in M$
W ... Wort in welches eingefügt werden soll, $W = (w_0, w1, ..., w{m - 1})$
insert(W, x):
for i = 1, 2, ..., k
W[h_i(x)] = 1
find(W, x):
for i = 1, 2, ..., k
if not W[h_i(x)]:
return false
return true
Der Speicheraufwand ist daher (erstaunlicherweise) exakt $m$ bit. Der Laufzeitaufwand ist dann höchstens ein vielfaches der aufwendigsten Hashfunktion aus $H$.
b
Disclosure
Die Ergebnisse wurden wie folgt berechnet:
strlst@ayaya ~ python3
Python 3.8.2 (default, Mar 24 2020, 03:08:36)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def h_1(k):
... return ((2**k) % 11) - 1
...
>>> def h_2(k):
... return ((5**k) % 11) - 1
...
>>> def h_3(k):
... return ((7**k) % 11) - 1
...
>>> numbers = [2, 4]
>>> [(h_1(n), h_2(n), h_3(n)) for n in numbers]
[(3, 2, 4), (4, 8, 2)]
>>> numbers2 = [3, 5, 6]
>>> [(h_1(n), h_2(n), h_3(n)) for n in numbers2]
[(7, 3, 1), (9, 0, 9), (8, 4, 3)]
$$ h_1(k) = (2^k mod (m + 1)) - 1, m = 10 $$ $$ h_2(k) = (5^k mod (m + 1)) - 1, m = 10 $$ $$ h_3(k) = (7^k mod (m + 1)) - 1, m = 10 $$
Es sollen nun 2 und 4 eingefügt werden. In der folgenden Tabelle sind die jeweiligen Worte und die darauf angewendeten Operationen festgehalten.
| Index | 0123456789 |
|---|---|
| Wort W | 0000000000, insert(2) |
| Wort W | 0011100000, insert(4) |
| Wort W | 0011100010 |
c
Es sollen nun 3, 5 und 6 gesucht werden. Die Bitmuster der einzelnen Eingangsdaten und des Wortes W sind folgende:
| Index | 0123456789 |
|---|---|
| 3 | 0101000100 |
| 5 | 0000000001 |
| 6 | 0001100010 |
| W | 0011100010 |
Wie sich erkennen lässt, scheiden 3 und 5 sehr schnell aus, weil sie bits enthalten, die unser Wort nicht enthält. find liefert also $false$. Aber W enthält alle bits, die die gehashte 6 enthalten würde. find liefert also $true$. Es handelt sich hier um ein false positive!
Aufgabe 5
a
In der offiziellen Python HowTo Seite (link) wird Timsort erwähnt und Wikipedia (link) verlinkt. Timsort haben wir in der Vorlesung kennengelernt, aber hier noch mal ein Auszug aus dem verlinkten Wikipedia Eintrag:
"Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] in GNU Octave,[6] on V8,[7] and Swift.[8]"
Aus der PHP Dokumentation (link):
"Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort. The pivot is chosen in the middle of the partition resulting in an optimal time for already sorted arrays. This is however an implementation detail you shouldn't rely on."
b
(Quelle für die Angaben (link))
Introsort verbindet drei Sortieralgorithmen, die jeweils ihre eigenen Vorteile haben. Zum Beispiel haben wir in der Vorlesung gehört, dass für wirklich wenige Elemente, Insertionsort sehr gut abschneidet. Dabei ist die Strategie bei Introsort nicht besonders kompliziert:
- verwende Quicksort
- ab einer gewissen Rekursionstiefe, wechsle für die derzeit betrachtete Menge zu Heapsort
- ab einer gewissen Untergrenze für die Anzahl der derzeit betrachteten Menge, wechsle zu Insertionsort
Mit diesem Ansatz wird Insertionsort für seine effizienten Fälle herangezogen, nämlich bei sehr wenigen Elementen. Bei sehr wenigen Elementen entsteht nämlich ein vergleichsweise großer Overhead bei anderen Algorithmen. Ähnlich ist die Situation für Quicksort. Im worst-case liefert Quicksort nämlich eine Laufzeitkomplexität von $O(n^2)$. Bevor das passieren kann, wird zu Heapsort gewechselt, um dennoch eine Laufzeitkomplexit von $(n \cdot log(n))$ zu gewährleisten. Dabei verhält sich diese Rekursionstiefe (also hängt ab von) logarithmisch zur Eingabegröße.
Introsort funktioniert zwar in place, ist aber nicht stabil.
c
Da bei herkömmlichen Bubblesort ein Wertepaar $(A[i - 1], A[i]), 0 < i < n$ nur getauscht wird, wenn gilt $A[i - 1] > A[i]$, werden gleichwertige Wertepaare nicht getauscht. Da zusätzlich bei herkömmlichen Bubblesort Implementierungen von links bis rechts iteriert wird, bleibt die Ordnung gleicher Elemente bestehen. Bubblesort ist also stabil.
Aufgabe 6
a
(durch pdflatex Formatierung könnten die Grafiken nicht an richtiger Stelle sein)
Wir sollen mithilfe einer Priority Queue (implementiert als Heap) und des Prim Algorithmus' den in Fig.1 abgebildeten Graphen zu einem Spanning Tree wandeln.
{ width=50% }
Der finale Spanning Tree lässt sich dann in Fig.2 observieren. Die Reihenfolge in der die jeweiligen Kanten hinzugefügt worden sind, lässt sich aus den individuellen Heap Stadien ablesen, aber zur lesbarkeit wurden diese Stadien auf die Kanten des Spanning Trees abgebildet.
{ width=50% }
Wie sich der Heap entwickelt lässt sich in Fig.3 observieren. Wobei der erste Heap eines Stadiums immer der initiale Zustand ist, der optionale Mittelschritt die updates der Kantengewichte und der letzte Schritt der Heap nach den Updates.
{ width=75% }
b
In diesem Fall sind wir konfrontiert mit Situationen in denen wir ein Element haben und dessen Heap Gewicht verringern wollen. In einer Array-Repräsentation werden die Heap Elemente vermutlich bewegt werden, also ist es schwer, rein durch clevere Ansätze das Problem zu lösen. Eine Datenstruktur aber, die in letzter Zeit sehr vielversprechende Performance für das Einfügen und Finden von Datensätzen gezeigt hat, könnte das Problem lösen: die Hashtabelle. Nämlich können Elemente selbst als keys und values verwendet werden. Benötigen wir ein bestimmtes Element, finden wir es einfach mithilfe der Hashtabelle und operieren weiter mit Heap Operationen darauf.
Klarerweise stellt dies einen erhöhten Speicherbedarf dar, aber auf die Laufzeit wirkt sich diese zusätzliche Datenstruktur positiv aus: sobald die Hashtabelle initialisiert ist (kann zur selben Zeit mit dem Heap mit derselben Laufzeitkomplexität des Heaps gemacht werden), können Elemente in nahezu konstanter Zeit gefunden werden. Selbst wenn Elemente aus dem Heap entfernt werden, könnte eine Hashtabelle, die bereits aus dem Heap entfernte Elemente nicht entfernt, dennoch dieselbe Effizienz beweisen.
Da die zusätzliche Laufzeitkomplexität der jeweiligen Hashtabellenoperationen nur additiv dazugezählt werden müssen, und die Laufzeit der Heap Operationen für eine Hashtabelle obere Schranken darstellen, präservieren wir die Laufzeitkomplexität der Heap Operationen.