Menu
It is called heap because it is a pile of memory space available to programmers to allocated and de-allocate. Every time when we made an object it always creates in Heap-space and the referencing information to these objects are always stored in Stack-memory.
First, we can always have duplicate values in a heap — there's no restriction against that. Second, a heap doesn't follow the rules of a binary search tree; unlike binary search trees, the left node does not have to be smaller than the right node!
A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types: Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it's children.
Min-Heap − Where the value of the root node is less than or equal to either of its children. Max-Heap − Where the value of the root node is greater than or equal to either of its children.
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.
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.
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
Actually, reading about the way memory is allocated (see Buddy Blocks) reminds me of a heap in data structures.
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
newis 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.
IMO it is merely an accident/coincidence that these two entirely unrelated things have the same name. Its like graph and graph.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With