0
$\begingroup$

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:

  1. A DEAP is a complete binary tree.
  2. The root contains no element.
  3. The left subtree is a minimum heap.
  4. The right subtree is a maximum heap.
  5. 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

The top shows the correct (expected behavior) deap while the bottom (current actual behavior) shows my version of the example of a deap

Many thanks in advance!

asked Feb 16 at 7:57
$\endgroup$

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.