Benjamins Blog

Unter einem Heap (im Deutschen gelegentlich auch als Halde bezeichnet) versteht man eine baumartige Datenstrukur mir einer besonderen Eigenschaft: Die Nachfolgeknoten jedes Knotens besitzen immer kleinere (oder immere größere) Schlüsselwerte als der Knoten selbst. Somit entsteht ein partiell geordneter Baum. Ein Heap wird vor allem für zwei Dinge eingesetzt: Zur Realisierung von gewichteten Prioritätswarteschlangen und zur Sortierung (Heap Sort).

Bei der Sortierung wird eine nicht geordnete Liste in einen binären Heap eingelesen und dabei entsprechend der Heapeigenschaft umstrukturiert. Danach ist die Wurzel genau der Knoten mit dem maximalen Wert, und alle Knoten jeweils kleiner als ihre Elternknoten, aber größer als ihre Kindknoten. Nun beginnt der eigentliche Sortierschritt. Iterativ wird immer der aktuelle Wurzelknoten aus dem Heap entnommen und an den sortieren Bereich angefügt. Danach wird der Heap wieder erneuert und ein neuer Knoten mit dem Maximalwert der übrigen Knoten wandert an die Stelle der Wurzel. Meistens wird diese Datenstruktur auf einem Array realisiert. Das Array wird zunächst in eine gültige Heap-Ordnung überführt. Danach wird jeweils der erste Werte als verbliebenes Maximun in den hinteren Bereich des Arrays einsortiert, wo schrittweise die Ordnung aufgebaut wird. Dabei wird einfach das Wurzelelement mit dem Element an der richtigen Stelle am Ende des Arrays getauscht. Nun wird erneuert der Heap korrigiert.

In der Visualisierung ist der binäre Heap als sogenannter Sunburst Tree dargestellt. Die Wurzel entspricht dem inneren Kreis, die Kindknoten jeweils den konzentrisch abstehenden Kreisbogensegmenten. Die Ordnung entspricht der farblichen Sortierung von Schwarz zu Rot. Im Video sind die einzelnen Phasen gut sichtbar. Zunächst wird die chaotische Ordnung durch eine Ordnung entsprechend des Heaps angepasst. Hier wandern die dunklen Felder nach innen und die roten Felder nach außen. Anschließend beginnt die Sortierung. Im Falle des ersten Elements bedeutet dies das Tauschen des dunkelsten schwarzen Feldes (Kreismitte) mit dem Ende des Arrays. Anschließend wird wieder die Heapstruktur hergestellt. Somit ensteht schrittweise die Ordnung - im Uhrzeigersinn und von außen nach innen.

Realisiert habe ich die animierte Visualisierung mithilfe von Java (zur Grafikgenerierung) und mencoder (Stopmotion). Auf vimeo gibt es außerdem das Video in hoher Qualität.

Zum Glück war ja vor kurzem Weihnachten, und mein Geburtstag ist auch nicht allzu lange her, hier ein paar Neuerwerbungen:

Donald A. Norman - The Design of Everyday Things

Ein Klassiker über Usability - insbesondere durch die alltagsnahen Beschreibungen sehr leicht zu lesen, dafür gibts am Ende doch einiges aus dem Bereich der kognitiven Psychologie und Usability Engineering. Das Buch wurde uns schon in Grundlagen interaktiver Systeme empfohlen und einige der Inhalte kommen mir sehr bekannt vor.

Edward R. Tufte - Envisioning Information

Ein wunderschönes Buch über die Visualisierung von Informationen. Das Buch stammt aus dem Jahre 1990 und deckt somit noch kaum den digitalen Bereich ab. Umso schöner sind die historischen Beispiele und Materialien.

Klanten, Bourquin, Ehrmann, et al. - Data Flow - Visualising Information in Graphic Design

Etwas leichtere Lektüre und sehr sehr anschaulich beschreibt dieses Buch Visualisierungen von Daten im Zeitalter von Processing & Co.

Nun ein seit langem überfälliger produktiver Beitrag: Schon seit längerer Zeit haben mich zirkuläre Visualisierungen fasziniert wie diese Weindatenbank oder diese Darstellung von Genomen. Ich habe deswegen selbst eine javabasierte Implementierung der Funktionalität erstellt und zum Testen ein altes Thema aufgegriffen - die Visualisierung von Freundeskreisen in sozialen Netzwerken.

Für die folgenden Grafiken wurden 335 Kontakte und über 2000 Bekanntschaften im StudiVZ ausgewertet und dargestellt:


Hierbei stehen Verbindungen für Bekanntschaften zwischen den verbundenen Personen. Je transparenter der ausgehende Verbindungsstrang einer Person ist, desto weniger Bekanntschaften besitzt sie. Die Personen wurden mithilfe eines clusterbildenden Algorithmus in Gruppen plaziert. Hierbei bilden Personen, die untereinander viele gemeinsame Freundschaftsbeziehungen einen benachbarten Bereich.



Für eine einzelne Person (hallo Cookie) sehen die Verbindungen zum Beispiel so aus:



Neben der Version mit den angegeben Benutzernamen habe ich noch eine Version mit den Benutzerkennungen der Personen erstellt, um zumindest außerhalb des Netzwerks für eine gewisse Anonymität zu sorgen:



Von dieser Variante gibt es auch eine große Version mit 4096 x 4096 Pixeln und 8 MB im JPEG-Format: Download: JPEG-Datei, 8 MB (Achtung groß!)

2002 sammelten Martin Dodge & Rob Kitchin in einem Buch namens "Atlas of Cyberspace" verschiedene, für damalige Zeit sehr innovative Visualisierungen des Internets. Dabei ging es sowohl um semantische wie auch geografische Aspekte. Sechs Jahre später gibt es nun den Inhaltes dieses Buchs kostenlos als PDF unter CreativeCommons-Lizenz.

Eine mit Processing realisierte Visualiserung zwölf verschiedener Sortieralgorithmen. Auf den Grafiken werden deutlich die Charakteristika der einzelnen Algorithmen sichtbar. Die normierte Zeitachse gibt jedoch keine Auskunft über die Zeitkomplexität der Algorithmen.

Neben den unten stehen Vorschaufotos gibt es außerdem große Grafiken:
Sorting Algorithm Visualization Poster I
(PNG, 1280 x 3691 px, 970 kB)
Sorting Algorithm Visualization Poster II
(PNG, 3072 x 2170 px, 1120 kB)

Außerdem eine Posterversion zum Drucken:
Sorting Algorithm Visualization Poster
(PDF, Din A1, 8885 kB)

...mit Processing:

Ich habe ein kleines Perl-Script geschrieben, dass rekursiv das StudiVZ durchforstet und daraus eine Grafik im SVG-Format mit den Freundschaftsbeziehungen erstellt:
SVG-Grafik (42 KByte) Vollständigen Artikel lesen...