Question

Let T be a complete binary tree such that node v stores the entry (p(v), 0), where p(v) is the level number of v. Is tree T a heap? Why or why not?

I know that a complete binary tree is a heap, but shouldn't we also take into consideration the values that it is storing into the tree: (p(v), 0)? The heap tree could be either a min-heap or max-heap. If we order the the value based of p(v) which is the level number of v, then it would result in a min-heap since the higher numbers are at the bottom. However, if we order the value based of the 0, then this could be a max-heap, where the highest value is at the top. I guess in both cases it would result in a heap tree, but I'm wonder if we can store 2 numbers into the heap tree because most of the examples I see in the book have a variable and a number (A,5) to make it clear that the order of the tree is based of the number.

Answer 1

Your query seems to be about what the nodes of the heap may contain. To know that you have to first know what a heap is used for. Usually there are two main puposes of a heap:

1. In heap sort. Since in a heap, we have a specific order of the values in the node (children have either lower values or higher values than their parent depending on if we have max heap or min heap). This information can be used to keep extracting the root of the heap and fixing the heap (to replace the extracted root). The result is that we get the elements in a sorted order.
2. As a priority queue. In this case, we order the nodes of the heap by priority. For example if every name that begins with M has higher priority than A which in turn has higher priority than T, then the root should have M, the child should have A and the subsequent child has T.

Obviously if only numbers are given and nothing is mentioned about priority order, then we assume that the max heap will have the highest number at the top.

Now think about the use of a priority queue. We have each node containing some amount of information and priority assigned to it. The highest priority is at the top. Children node have lower priority than parent node. Is there any real use of a "priority number/order" if there is no other information associated with the node? No. Rather we associate "priority number" to other information.

In fact, the following are also valid nodes for construction of a heap:

Names of the students in your class prioritized by their roll numbers.

Notice that the nodes above have a lot more information than just two fields.

The priority order doesn't need to be a number. It can be any entity as long as we can establish a order for it. As long as we know that entityX is lower than entityY, we can estasblish a priority order and create the heap.

In the example you gave in the question, we can assume that the priority order of the nodes of the tree can be established by "level number" and it will become a heap. You can also prioritize the nodes by the second field "0" and call it a heap.