Why is the heap data structure called 'heap'?

Question

The term "heap" has majorly two meanings in computer science -

1. The "heap" memory in the context of memory management.
2. The "heap" data structure as the representation of a priority tree as an array.

I can understand the use of the word "heap" in the context of memory as it correlates to the literal meaning of the word.

However, the use of the word "heap" for an array representation of a tree is not obvious to me.

Although I have never come across any explanation for using this word in any textbooks or lectures, it would be interesting if someone here could present an explanation for the usage, ideally with citations to resources.

Answer 1

It seems that the use of heap to denote a priority queue implemented as an implicit binary tree was first introduced in the original Heapsort article: Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348.

A well-known chatbot gives the following explanation: "Williams chose to call this data structure a "heap" because of its resemblance to a heap of pebbles or stones, with the largest or smallest stone at the top, depending on the type of heap." Unfortunately, no reference substantiates that.

Answer 2

In the book The Algorithm Design Manual$^{[1]}$, the author writes:

Power in any hierarchically structured organization is reflected by a tree, where each node in the tree represents a person, and edge $(x, y)$ implies that $x$ directly supervises (or dominates) $y$. The person at the root sits at the “top of the heap.”

Then in the next paragraph, he continues:

In this spirit, a heap-labeled tree is defined to be a binary tree such that the key of each node dominates the keys of its children. In a min-heap, a node dominates its children by having a smaller key than they do, while in a max-heap parent nodes dominate by being bigger.

Therefore, I think we can draw the conclusion that, in the heap data structure, the notion of heap is used to represent some number of items that we don't necessarily care about as our primary goals are to insert and extract-min/max.

---

$[1]$ Skiena, S.S. (2020). Sorting. In: The Algorithm Design Manual. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-54256-6_4

Answer 3

There's nothing to explain. It's just a name. Instead of "heap", the name could have been "giraffe" or "hxfq" or anything else. A rose by any other name is still a rose.

The definition of a heap data structure is found in standard references, e.g., https://en.wikipedia.org/wiki/Heap_(data_structure).