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

Question

A heap is a tree data structure where higher levels of the tree always contain greater (or lesser, if it's set up that way) values than lower levels. "The" heap is a bunch of free RAM that a program has available for dynamic allocation. They're both called "heap," but what does the one have to do with the other?

Egerton

See this very site for an exploration of the origin of the name "heap" for the free store of memory. – Predisposition

Related posts here and here – Centonze

Its broken english. Sorry "broken english" is tautology. Just English – Berky

Answer 1

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...

Spry

"the description heap is most appropiate because "greater" objects are placed higher up in the tree" - you call "heap" most appropriate, and then at the end call it tree. At this point I give up. – Berky

It’s still a tree data structure. A specific kind of one that’s called a “head”. There’s clearly no inconsistency. Evidently the great majority of people who read this understand this much, so the issue seems to be on your end. – Spry

Answer 2

They both have the same name, that's about it.
There 'the heap' is never arranged as an actual heap data structure.

Chockfull

Answer 3

The heap (datastructure) is called like that because if you draw it it looks like a heap. The heap (memory) is called a heap because it is somehow organized but not fully. You accumulate data on a heap but you might have holes in it and irregularities. It's as if you'd put papers on a heap. Sometimes you remove one from the bottom. This has a form of a heap, i.e. somehow organized but not fully.

Laverty

"if you draw it it looks like a heap" -> what is meant by the the predicate noun of "...it looks like a heap"? – Peony

You know: just by looking at it, you can tell it's a heap, because of the way that it is. ;) – Rappee

Answer 4

Nothing. No relation.

Slaughter

Answer 5

The only relationship between the two is the name "heap."

Biancabiancha

Answer 6

To futher complicate the question: on some systems (e.g. Microsoft Windows), there are multiple "heaps" in the memory allocation sense. "The" heap is merely the default heap. But if you call HeapAlloc(), you can choose from which memory allocation you want a sub-allocation.

Horning

Answer 7

For the data structure, I would second the answer from I. J. Kennedy

Heap connotes a vertical structure

The concept to remember here is height.

The unfortunate thing about using this term is that most of us understand "heap" to mean a disorganized pile, and indeed that is the intended mental image for the memory heap (this memory storage is not contiguous in RAM, unlike the stack).

We mostly implement order into heaps (think min heap and max heap) rather than simply throwing data into them ad hoc. However, if order is not used, heap is the more general term. IMO, tree feels a more natural term for this, but I think intuitively people envision bifurcation when they hear "tree" and the important concept to remember with this structure is "depth" and "height" since we typically speak of "balancing a heap" or different "depth levels" of a heap.

Rome

Answer 8

Definition from answers.com

Heap: A group of things placed or thrown, one on top of the other: a heap of dirty rags lying in the corner.

It's just basic naming due to the conceptual image of throwing things in an unordered fashion. As other posters point out, the heap is not organized as a heap data structure. That depends on the memory allocation routines in your system library (eg. check how malloc works)

Thacker

Answer 9

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.

Saintsimon