What is the origin of the term “heap” for the free

Question

I am trying to find the official (or a good enough) reason that the free store is commonly referred to as the heap.

Except for the fact that it grows from the end of the data segment, I can't really think of a good reason, especially since it has very little to do with the heap data structure.

Note: Quite a few people mentioned that it's just a whole bunch of things that are kind of unorganized. But to me the term heap physically means a bunch of things that are physically dependent on one another. You pull one out from underneath, everything else collapses on it, etc. In other words, to me heap sounds loosely organized (e.g., latest things are on top). This is not exactly how a heap actually works on most computers, though if you put stuff towards the beginning of the heap and then grew it I guess it could work.

Answer 1

It's unordered. A "heap" of storage.

It isn't an ordered heap data structure.

Answer 2

Heap usually has these features:

1. You can't predict the address of a block malloc() returns.

2. You have no idea of how the address returned by the next malloc() is related to the address of the previous one.

3. You can malloc() blocks of variable sizes.

So you have something that can store a bunch of blocks of variable sizes and return them in some generally unpredictable order. How else would you call it if not "heap"?

Answer 3

I always figured it was kind of a clever way of describing it in comparison to the stack. The heap is like an overgrown, disorganized stack.

Answer 4

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)

Answer 5

It's named a heap for the contrasting image it conjures up to that of a stack.

• In a stack of items, items sit one on top of the other in the order they were placed there, and you can only remove the top one (without toppling the whole thing over).

  

• In a heap, there is no particular order to the way items are placed. You can reach in and remove items in any order because there is no clear 'top' item.

  

It does a fairly good job of describing the two ways of allocating and freeing memory in a stack and a heap. Yum!

Answer 6

I don't know if it is the first but ALGOL 68 had keyword 'heap' for allocating memory from the free memory heap.

The first use of 'heap' is likely to be found somewhere between 1958, when John McCarthy invented garbage collection for Lisp and the development of ALGOL 68