Why are two different concepts both called "heap"? [duplicate]

Question

Why are the runtime heap used for dynamic memory allocation in C-style languages and the data structure both called "the heap"? Is there some relation?

Linneman

duplicate question? https://mcmap.net/q/21778/-what-39-s-the-relationship-between-quot-a-quot-heap-and-quot-the-quot-heap – Mozellamozelle

Go to an English dictionary and count the number of entries under "Run". How many of the 40+ entries apply to computers? :) – Balkan

A related post here w.r.t. runtime heap used for dynamic memory allocation. – Tuba

Answer 1

Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435):

Several authors began about 1975 to call the pool of available memory a "heap."

He doesn't say which authors and doesn't give references to any specific papers, but does say that the use of the term "heap" in relation to priority queues is the traditional sense of the word.

Frangipane

Pool would be a better name than heap. – Epithalamium

Interesting. Someone should ask him if he remembers which authors. – Shonna

Wikipedia claims that it's because at an early stage Lisp used a heap (data structure) to implement its memory store. It doesn't say how. Its reference is "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.", which I don't have. – Cai

I have no reference for this but my guess would be that initially the data structure used to organize references to open blocks of memory was a min heap. Seems like it would be at least a decent way of quickly finding the smallest block of memory that would allow you to store the data you were trying to store Update: What I said sounds exactly like buddy blocks en.wikipedia.org/wiki/Dynamic_memory_allocation#Buddy%5Fblocks – Prolate

@SteveJessop - Checking Cormen, Leiserson, Rivest, Stein - 3rd edition (2009) at the start of Heapsort chapter it only says 'The term "heap" was originally coined in the context of heapsort, but it has since come to refer to "garbage-collected storage," such as the programming languages Java and Lisp provide. Our heap data structure is not garbage-collected storage, and whenever we refer to heaps in this book, we shall mean a data structure rather than an aspect of garbage collection.' CLRS - 2nd edition also has almost exact same phrasing (no indication that Lisp used a Heap). – Derivative

Also en.wikipedia.org/wiki/… discusses how there's lack of evidence for that old anonymous citation and the pages on dynamic memory allocation doesn't talk about lisp or Cormen et al any more. – Derivative

Donald is right and this is an unfortunate naming conflict. Particularly for non native speakers, e.g., yours truly, that their first encounter with the word "heap" was in their data-structure course. I have called it heap, always thought it was heap-like structure until today when I decided to understand how a heap-like structure is used for memory allocation. I'm mildly infuriated :/ – Iinde

Answer 2

They have the same name but they really aren't similar (even conceptually). A memory heap is called a heap in the same way you would refer to a laundry basket as a "heap of clothes". This name is used to indicate a somewhat messy place where memory can be allocated and deallocated at will. The data structure (as the Wikipedia link you reference points out) is quite different.

Nipha

Yes, I think that's rather the point on which he's basing his question: they are different. So why are they called the same thing -- is there some underlying relation. – Selfrenunciation

The way I interpreted this answer is "no, there is no underlying relation", so it answers the question. – Ambroseambrosi

Andrew is answering that. There's no relation. Just a coincidence. The memory heap is more true to the common usage since memory is allocated as if a "heap of clothes". The data structure however demanded a larger stretch of imagination. And this becomes a rather much more interesting "why". The name comes from the fact nodes are arranged by their key and a parent node key is always >= than its child node. – Accordingly

They are definitely unrelated. However the problem with calling it "the heap" is that "the heap's" counterpart--"the stack"--is also an actual stack. – Isochronism

I know why the heap data structure is called a heap: because it satisfies the heap property. But why is the heap property called such? It makes no sense to me, as a name like "top heavy" would be much better. – Faultfinder

Answer 3

The name collision is unfortunate, but not all that mysterious. Heap is a small, common word used to mean a pile, collection, group, etc. The use of the word for the data structure pre-dates (I'm pretty sure) the name of the pool of memory. In fact, pool would have been a much better choice for the latter, in my opinion. Heap connotes a vertical structure (like a pile), which fits with the data structure, but not the memory pool. We don't think of a memory-pool heap as hierarchical, whereas the fundamental idea behind the data structure is keeping the largest element at the top of the heap (and sub-heaps).

Heap the data structure dates back to the mid-60s; heap the memory pool, the early-70s. The term heap (meaning memory pool) was used at least as early as 1971 by Wijngaarden in discussions of Algol.

Possibly the earliest use of heap as a data structure is found seven years earlier in
Williams, J. W. J. 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7(6): 347-348

Accusal

Yes, but a heap also implies disorder and memory heaps are generally disordered. The data structure heap is extremely well ordered. So again there's an equal mismatch going the other way based on the common definition of heap. – Balkan

It's always introduced as the opposite of stack which should suffice to explain the name IMO. – Myongmyopia

It's not coincidence -- the free list can be implemented as a priority queue via a binomial heap. – Dimpledimwit

@jmucchiello: a heap of logs (see picture) is well ordered and tree-resembling. This is the origin of the data structure's name according to one of my undergraduate textbooks. – Ninanincompoop

TL;DR; Broken english :) – Rayon

It'd be great if the CS community could set up a standards body for these kinds of naming conventions. We should absolutely rename OS heaps to "pools" – Grandson

Answer 4

Actually, reading about the way memory is allocated (see Buddy Blocks) reminds me of a heap in data structures.

Lancers

My comment on Peter Zhang's answer is also relevant here. The binary buddy system can be represented as a binary tree, and it also looks as a valid max heap does when the "key" of each node is the total memory underneath it (but these values are implicit and never change). Neither the allocation nor freeing algorithm use heap operations on this binary tree, as far as I can tell. – Slew

Answer 5

Heap-like data structure is used by algorithm of finding available memory allocation. The following is excerpted from http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

When new is invoked, it starts looking for a free memory block that fits the size for your request. Supposing that such a block of memory is found, it is marked as reserved and a pointer to that location is returned. There are several algorithms to accomplish this because a compromise has to be made between scanning the whole memory for finding the smallest free block bigger than the size of your object, or returning the first one where the memory needed fits. In order to improve the speed of getting a block of memory, the free and reserved areas of memory are maintained in a data structure similar to binary trees called a heap.

Celerity

I'm extremely skeptical of this, specifically "... the free and reserved areas of memory are maintained in a data structure similar to binary trees called a heap." It sounds to me like the author is guessing there's a connection, based on the name "heap", and is probably mistaken. Can anyone confirm/refute? – Elmaleh

After some light research on the Binary Buddy system (used in Linux), it can be represented by a binary tree due to how it partitions data. This binary tree looks like a valid max heap if you observe the nodes in terms of total memory, but nodes aren't inserted into this binary tree as they are in a max heap - nodes are inserted directly in the smallest leaf of free memory >= the requested size. 1 2 3 – Slew

Answer 6

IMO it is merely an accident/coincidence that these two entirely unrelated things have the same name. Its like graph and graph.

Pin

The two graphs can though somehow be related. Imagine the graph of a function as follows: The tuple domain,range) is a vertex and a edge connects two such vertices – Skeens

@Amit: For continuous graphs that would mean an infinite number of vertices. This is ok, but that also makes the concept of edges between the vertices meaningless. In the graph of the function f(x)=x*2, is there an edge between (0,0) and (1,2)? If yes, how about (0,0) and (0.5,1)? (0,0) and (0.25,0.5)? There is no way of having the concept of an edge between vertices, so this is not really a graph. – Pin

Answer 7

The colloquial terms stack memory and heap memory are not used in the C++ standard. The standard uses static storage, thread storage, automatic storage, and dynamic storage.

More can be found at Storage Duraction section of the standard.

Hence, from the language and standard library point of view, there is no confusion.

Drinkable

Answer 8

Q. What is a heap? A. A heap is a collection of objects place on top of each other.

Answer to your question: Both memory heap and binary heap uses the same concept as you know. Data is stored in the form of a heap in the memory in the same order as written in the program whereas binary heap is a data structure that follows the same concept of storing data in an ordered way in the form of a heap(Data on top of the other). Let me know what you think in the comments section.

Irv

Both memory heap and binary heap uses the same concept as you know. Memory heap and the heap data structure do not have anything in common – Reduplicative

Answer 9

Perhaps the first memory heap implemented was managed by a heap structure?

Owensby

That hypothesis doesn't seem at all obvious - how is a heap (the data structure) at all useful for maintaining a heap (the dynamic memory region)? – Gamete

-1. I would prefer an authoritative statement with evidence instead of what's obviously just a guess. – Skipp

Highly unlikely. There seems to be no good reason to use a heap (the data structure) to manage the heap (the pool of free memory). – Geothermal

Certainly the first heap was not managed with a heap structure — memory was too precious in those early days to spend on managing other memory, and too small to need it. Also, the data structure was introduced in 1964, well after the first machines that had what we'd now call heap memory. But it's also not crazy to think of using a heap structure as a priority queue to quickly find the smallest available block that meets the allocator's needs. – Runyan