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

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.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!