#4 Heap

One of my most favorite data structures are Heaps. On the one hand, they are great for queing items dynamically by assigned priorities. On the other hand they are used for a quiet performand sorting algorithm with a complexity of $O(n \log n)$.

Heaps always fullfill the following two properties after termination of an arbitrary but defined operation: The Heap structure and the Heap Order. A Heap is usually displayed as a graph. The Heap Structure is best explained by "filling the tree from left to right and from top to bottom". The picture above might make this clearer. We have $A$ a as a graph, fullfilling the Heap Property and $B$ where the Heap Property is violated.

The Heap Order demands that every vertex $v$ in the graph, having vertex $w$ above it (assuming a so called Min-Heap that has a vertex with minimum priority as the Root Vertex), has a priority higher than or equal to $w$, so explicitly priority($v$) $\geq$ priority($w$).

Every time a vertex is removed or inserted, the Heap Order might be violated so repairing the Heap is necessary. Vertecies either swap multiple times with their parent vertex (recursively) or with their child vertex until the Heap Order is established again.

What I just (roughly) outlined is called Binary Heap. There are many other kinds of Heaps. A kind of Heap I found to be worth exploring is the Fibonacci Heap (or if you prefer something more practical the Pairing Heap).