Is it possible for both children to be the same value?


#1

Question

In the context of this exercise, is it possible for both children to be the same value?

Answer

If the heap allows for duplicate elements, yes, this is absolutely possible. In fact, a heap can consist of just the same element, so that all parent and child elements are the same value.

When there are matching child elements, and heapify down is run, it will select either child element, depending on how you implemented the function. Usually, it will select the right one, since the comparison is usually done on the left child first then it will check the right child after.

If the heap does not allow duplicate elements, however, this is not possible. For example, say you have a priority queue, which utilizes a min-heap underneath, representing a line in a restaurant. In this line, two people cannot share the same place, so their keys must be unique. If we drew this heap as a tree, then we can see how every element is unique, and as a result, no two children elements are the same.