Why Are Two Different Concepts Both Called "Heap"

Why are two different concepts both called heap ?

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.

What's the relationship between a heap and the heap?

Nothing much, to be honest. I would imagine that the word heap was simply taken with it's everday (non-technical) usage and applied to these two concepts individually as reasonably good analogies.

In the first case (tree data structure meaning), the description heap is most appropiate because "greater" objects are placed higher up in the tree (where "greater" is determined by an arbitrary key function) - i.e. there's a sort of piling of smaller objects on top of larger ones (or larger on top, depending how you think of it). This is just how I'd interpret it; whoever first applied the name heap to this data-structure thought it was an appropiate name in his mind, and it's just stuck.

In the second case (chunks of RAM), the name of heap is maybe a bit more evident. "Heap" is just "a large collection of things in a highly arbitrary order" here, which would seem to apply just as well in common usage as it does to dynamically allocated chunks of memory.

In any case, I wouldn't worry about the abstract metaphorical similarities you can draw between the two ideas. Treat them completely seperately and you won't go wrong in any situation.

Edit: It seems the tree-based data structure may have taken its name from the heap of abstract algebra, as is reasonably common within computer science. However, I wouldn't want to confirm or deny this...

What's the relationship between those two “heaps”?

As far as I know, they just happen to have the same name.

One 'heap' is the data structure that contains, at its head, the greatest element of a collection. Since its children just have to be smaller than it, it is a semi-sorted collection. This is more efficient than maintaining a fully sorted list in certain circumstances, such as when you're commonly interested in only the largest element. http://en.wikipedia.org/wiki/Heap_(data_structure)

The other 'heap' is the place in memory besides the stack data can be stored. The problem with data stored in the stack is that it will be freed, and thus lost, when the function returns, and on top of that the stack can only hold so much before overflowing. The 'structure' of the heap is usually a linked list of free data segments - malloc looking for a data segment that satisfies the size requirements, marking it as in use and returning it, whereas free looks for the header for that data segment in the heap, marks it as unused and puts it back in the linked list of free data segments. (Other optimizations include things like having dedicated linked lists for certain chunk sizes.)

As you can see - not related at all!

Is the heap actually a heap?

No, the heap is not a heap-ordered binomial tree at all. It's not clear (to me) whose fault the terminology clash is, but both uses of heap date back decades now (mid-1970, it appears). Some of the history is discussed in this article.

Memory Heap vs. Min/Max Heap Data Structure

heap is a data structure which is actually a complete binary tree with some extra properties.
There are 2 types of Heaps:

1. MIN Heap
2. MAX Heap

in min heap the root has the lowest value in the tree and when you pop out the root the next lowest element comes on the top. To convert a tree into heap we use heapify algorithm.
It is also know as priority queue in c++. and usually as a competitive programmer we use STL function for heap so that we dont have to get into the hustle of creating a heap from scratch.
Max heap is just the opposite with largest at the root.
Usually heap is used because it has a O(logN) time complexity for removing and inserting elements and hence can even work with tight constraints like 10^6.

Now i can understand you confusion between heap in memory and heap data structure but they are completely different things. Heap in data structure is just a way to store the data.

What's the connection between the heap used in dynamic memory allocation and the data structure?

Heap is a synonym for what the standard calls the free-store. In contrast to stacks, which is used for function calls, and function-local object storage, heaps grow in the opposite direction (top to bottom) on many implementations (as opposed to stacks -- which grow from bottom to top). Of course, none of these are required by the standard.

The heap data structure, on the other hand is completely different -- it is a specialized tree structure with certain properties.

It is possible some implementations use the heap data structure for free-store management, whence the name may have been derived. (See buddy memory allocation.)

What is the origin of the term heap for the free store?

Knuth rejects the term "heap" used as a synonym for the free memory store.

Several authors began about 1975 to call the pool of available memory a "heap." But in the present series of books, we will use that word only in its more traditional sense related to priority queues. (Fundamental Algorithms, 3rd ed., p. 435)

Why did heap memory come into existence?

With stack allocation there is a strict LIFO (last-in, first-out) policy for the lifetimes of allocated objects. That is, if you allocate object A, then object B, then object C, they will always be freed in the opposite order.

That's useful in a lot of cases, but there are also cases where you e.g. want object C to continue to exist after B and A have been destroyed. There's no way to do that with a stack, so to handle those cases the heap was introduced. It's harder to use correctly than stack allocation, but also more flexible/powerful.

a stack vs the stack and a heap vs the heap

"The stack" and "the heap" are memory lumps used in a specific way by a program or operating system. For example, the call stack can hold data pertaining to function calls and the heap is a region of memory specifically used for dynamically allocating space.

Contrast these with stack and heap data structures.

A stack can be thought of as an array where the last element in will be the first element out. Operations on this are called push and pop.

A heap is a data structure that represents a special type of graph where each node's value is greater than that of the node's children.

On a side note, keep in mind that "the stack" or "the heap" or any of the stack/heap data structures are unique to any given programming language but are simply concepts in the field of computer science.

---

Related Topics