I've been working with the doubly-ended array-based priority queue (DEAP) data structure and this problem has been giving me a pain in the neck. I want to know if the DEAP for a given data set is uniquely determined, or if there exist more than one DEAP representation for the data set. Especially, if there are multiple correct ways of populating a DEAP, I am wondering if the example of the DEAP as shown in the textbook just happens to be initialized in that specific way.
The below paragraph explains the property of a DEAP:
- A DEAP is a complete binary tree.
- The root contains no element.
- The left subtree is a minimum heap.
- The right subtree is a maximum heap.
- If the right subtree is not empty, then let i be any node in the left subtree. Let j be the corresponding node in the right subtree. If such a j does not exist, then let j be the node in the right subtree that corresponds to the parent of i. The key in node i is less than or equal to that in j.
Especially, both top and bottom trees with captions "expected behavior" and "current actual behavior" satisfy Property 5 as shown by the comparisons in blue curves, so shouldn't the bottom tree also be valid?
The DEAP as shown in the textbook
Many thanks in advance!