# Relation Between Priority Queue, Heap, Tree

There are $$2$$ "basic"/"fundamental" data structures due to the way memory works:

1. array

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

1. array
2. tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $$\subset$$ tree $$\subset$$ priority queue?

• What is ⊂ intended to mean or represent in this context?
– D.W.
Jan 22 '20 at 17:00
• @D.W. $\subset$ for example, a tree can be built from array or linked list but not the opposite Jan 28 '20 at 10:10
• @KyleJones ADT=Abstract Data Type unlike array or linked list Jan 28 '20 at 10:11
• Do you have any reference where these concepts are formally defined? Jan 28 '20 at 10:26

Arrays and linked lists are indeed simple data structures, but they are not more "fundamental" than other data structures. Everything in software is built out of contiguous memory to which the CPU has random access by address. All data structures are just abstractions built on top of that foundation.

A tree data structure is not composed of arrays and linked lists in any meaningful sense. You can implement a tree data structure using contiguous memory and pointers, just as you can implement a linked list using contiguous memory and pointers. If anything, a linked list is a special case of a tree in which each node has at most one child.

Saying that a tree is built from linked lists is like saying that a dinosaur is built from birds.

• It is confusing a special case as a composition. A dinosaur is not composed of birds; a bird is a special case of dinosaur. A tree is not composed of linked lists; a linked list is a special case of tree.
• However, the special case is itself only in a technical sense. If someone casually mentions the word dinosaur, they probably aren't thinking of birds. If someone casually mentions the word tree, they probably aren't thinking of linked lists.

You are also confusing the definition of abstract data type. An abstract data type is one where the operations are specified but the implementation is unspecified. A priority queue is an abstract data type, for which many concrete implementations are possible. Possible implementations of a priority queue include ones based on heaps stored in tree data structures; heaps stored in implicit trees in resizable array data structures; binary search trees; and many others. A linked list is an example of a concrete data structure which can be used to implement (among other things) a list abstract data type with operations for insertion, removal, indexing, etc.

• Another strong disagree from me about what constitutes "basic"/"fundamental". If "fundamental" structures are analogous to the classical simple machines (pulley, inclined plane, screw, etc), they would probably be the structures implied by category theory, such as product types (i.e. structs/records), sum types (i.e. variant records/disjoint unions), exponential objects (i.e. closures), etc. Jan 30 '20 at 3:10

It is a matter of perspective.

About "basic" data structures. Indeed array and linked list are fundamental data structures, two different implementations of the linear lists, of which stack and queue can be seen as offspring.

But you should also view array and links as basic tools to build other data structures, and sometimes they can be combined (I think hash tables with buckets use both constructs).

About priority queues and the-like. The binary heap I always consider to be a data structure that exists on so many levels. Distinguishing them helps in understanding the heap, but also makes you aware of these levels when looking at other data structures. The levels match most of your diagram, but the meaning of your symbol $$\subset$$ needs some explanation.

(1) Top level is the priority queue. It is an abstract data structure that contains pairs of data+priority. The (main) operations are "isEmpty", "insert", and "deleteMax".

There are several implementations of the ADT priority queue, each of them motivated by better complexity of the operations, or sometimes simplifying earlier complicated constructions.

(2) The binary heap is perhaps the most well known of these implementations. It is a complete binary tree, where the priority values are partially ordered: nodes have larger priority than their children, but there is no order between left and right subtrees. The standard ADT operations are implemented by moving the appropriate items along the tree, swapping nodes with parents or children when they have conflicting priority values.

However, although these operations are understood as if in a tree, their actual implementation does not use pointers/links as usual.

(3) As the tree used here is complete, its nodes can be mapped onto positions in an array, and rather than following pointers to parent and children, we compute their address. In this level, the binary heap is linear after all.

While I'm accepting the @Rotenberg's answer,

I think instead of think of the linked-lists, go one level deep and think about this in a linked nodes (linked objects or linked memory addresses) perspective which is what the real building box here. For arrays, the building box would be indexes (which again are memory addresses with content, but not linked to each other). Although Linked List Nodes are connected to each other (Nodes have their neighbors' addresses in them as pointers), Arrays doesn't have that. In memory, the indexes are continuously back to back and they don't contain the neighbor addresses within them

In that way it would be easy to think about the relationship between these data structures.

Now, as linked lists are built from nodes, trees are also built from nodes, just having a different structure. In special cases for tree, that structure becomes the same as @Rotenberg stated above.

In this image, it's a tree with only left childs for each node. Although it looks like a linked-list, we can't say it's a linked-list, because of the content of nodes. Even though they could be null as in shown image, there are two child pointers and one parent pointer for each node in a tree where in a linked-list, it's only two pointers for each node. So technically, it's not a linked-list.

So, considering this node approach, you can't really say that linked-lists are a subset of Tree structure. Both of them are just a collection of nodes connected to each other with different policies.

But, when it comes to heap and tree, you can say that heap is a special case of tree which is when a tree is a complete tree and also you can say that a heap is a subset of tree.

• (1) You might want to clarify the point that arrays are not defined in terms of linked nodes. Even in functional languages with built-in algebraic data types such as Haskell, array types still have to be added as separate library primitives for performance reasons. Jan 28 '20 at 21:50
• (2) A binary tree is a specific type of tree, but there are other types of tree data structures with different—even variable—numbers of child nodes such as B-trees. A linked list could be considered a trivial "unary tree" (although, as I stated in my answer, this is not usually how people think). Jan 28 '20 at 21:50
• (3) A heap is not just a complete tree; it also has a partial ordering guarantee. Also, the term "heap data structure" is ambiguous. There are multiple ways of implementing a heap in memory, some of which involve explicit linked tree nodes and some of which do not and only involve array storage. See en.wikipedia.org/wiki/Heap_(data_structure)#Implementation Jan 28 '20 at 21:53
• @AaronRotenberg (1) What I meant was, Although Linked List Nodes are connected to each other (Nodes have their neighbors' addresses in them as pointers), Arrays doesn't have that. In memory, the indexes are continuously back to back and they don't contain the neighbor addresses within them. Jan 29 '20 at 20:19
• @AaronRotenberg (3) Yes. It has many ways of implementing. But, one way is to implement a complete tree and that was my point. Since it is a way, it falls into a subset of trees regardless of there are other ways. Thank you for the reference. Jan 29 '20 at 20:25