What is the precise definition of the Heap data structure?

Question

The definition of heap given in wikipedia (http://en.wikipedia.org/wiki/Heap_(data_structure)) is

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children (min heap)

The definition says nothing about the tree being complete. For example, according to this definition, the binary tree 5 => 4 => 3 => 2 => 1 where the root element is 5 and all the descendants are right children also satisfies the heap property. I want to know the precise definition of the heap data structure.

Apparent

I suspect Wikipedia gave the precise definition and the example you cited is a heap. – Exposure

A poorly balanced binary heap does not stop it from being a heap. – Gat

Answer 1

As others have said in comments: That is the definition of a heap, and your example tree is a heap, albeit a degenerate/unbalanced one. The tree being complete, or at least reasonably balanced, is useful for more efficient operations on the tree. But an inefficient heap is still a heap, just like an unbalanced binary search tree is still a binary search tree.

Note that "heap" does not refer to a data structure, it refers to any data structure fulfilling the heap property or (depending on context) a certain set of operations. Among the data structures which are heaps, most efficient ones explicitly or implicitly guarantee the tree to be complete or somewhat balanced. For example, a binary heap is by definition a complete binary tree.

In any case, why do you care? If you care about specific lower or upper bounds on specific operations, state those instead of requiring a heap. If you discuss specific data structure which are heaps and complete trees, state that instead of just speaking about heaps (assuming, of course, that the completeness matters).

Pyrogallate

Thanks. I just wanted to clarify if a heap implementation had to be necessarily complete. Also, I think you are referring to the Priority Queue as the ADT and the heap/binary heap being implementations. – Apparent

@Apparent Yes, some people (including me at times) treat priority queue (the ADT) and heap (the category of data structures, which happen to work well as priority queues) as the same thing. – Pyrogallate

Answer 2

Since this question was asked, the Wikipedia definition has been updated:

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete¹ tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.² The node at the "top" of the heap (with no parents) is called the root node.

However, "heap data structure" really denotes a family of different data structures, which also includes:

• Binomial heap
• Fibonaicci heap
• Leftist heap
• Skew heap
• Pairing heap
• 2-3 heap

...and these are certainly not necessarily complete trees.

On the other hand, the d-ary heap data structures -- including the binary heap -- most often refer to complete trees, such that they can be implemented in an array in level-order, without gaps:

The 𝑑-ary heap consists of an array of 𝑛 items, each of which has a priority associated with it. These items may be viewed as the nodes in a complete 𝑑-ary tree, listed in breadth first traversal order.

Carnay