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ß!)

... mit Context Free:


Originalgröße (2048 x 2048 Pixel, 1,95 MB)


Originalgröße (2048 x 1280 Pixel, 183 KB)


Originalgröße (2048 x 2048 Pixel, 4,52 MB)


Originalgröße (2048 x 2048 Pixel, 1,60 MB)

Die Grafiken basieren auf Regelsammlungen und werden durch kontextfreie Grammatiken randomatisiert generiert.

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:

Da die letzten Wochen ja zu einer geschenkreichen Zeit gehörten, bin ich nun unter anderem stolzer Besitzer dieser beiden englischen Bücher:


Und diese beiden Bücher passen nicht nur optisch wegen ihres Covers gut zusammen, sie behandeln beide den Themenkomplex Programmierung & Ästhetik. Während "Beautiful Code" darauf abzielt, anhand von kleinen Geschichten mit Beispielen aufzuzeigen, was Programmiercode und Algorithmen "ästhetisch" macht, behandelt das Processing-Buch von Reas und Fry den gleichnamigen Java-Dialekt zur Visualisierung und dem Design von Informationen. Insbesondere im Kontext der Medieninformatik zwei sehr gute und lesenswerte Bücher!

... und ein bisschen mehr Technik. Urban Art at it's finest:




Insbesondere das Tic-Tac-Toe-Spielen würde auf der einen oder anderen Hörsaalwand auch mächtig Spaß machen!