Heap Datastructure vs. Heap Dictionary Definition
In computer science, a heap is a specialized tree-based data structure. The nice thing about it is that it satisfies a very simple law, namely:
- If B is a child node of A, then key(A) ≥ key(b)
This simple law implies that the element with the greatest key is always in the root node.
There is a sort algorithm, namely Heap Sort, which utilizes this datastructure in order to achieve a worst case runtime of O(n log n), which is better than Quicksort for example.
Since the heap datastructure has such a nice property which makes it so useful, I looked the word up in the dictionary and what I found was quite amusing:
- heap: a collection of things in an untidy pile or mass…
Now I can understand the pile or mass part, since a tree can also somehow be seen as a pile, but untidy? That is a bit awkward and funny if you consider it from a computer science perspective.
I guess there is no Algorithms and Datastructures class out there where the Lecturer would call a binary heap untidy ;-)
Sources:
