Can max / min heap trees contain duplicate values?

Question

I am wondering if it is allowed to have maximum or minimum heap tree to have duplicate values? I could not find information about this only with the help of online resources.

Answer 1

Yes, they can. You can read about this in Introduction to Algorithms (Charles E. Lazerson, Clifford Stein, Thomas H. Cormen, and Ronald Rivest). According to the definition of binary heaps on Wikipedia:

All nodes are either [greater than or equal to] ( max heaps ) or [less than or equal to] ( min heaps ) each of their children, according to the comparison predicate defined for the heap.

Answer 2

Yes, they may have duplicates. From wikipedia heap definition:

Either the keys of the parent nodes are always greater than or equal to those of the children and the highest key is in the root of the node (this type of heap is called the maximum heap), or the keys of the parent nodes are less than or equal to those who have children, and the youngest is in the root folder of the node (minimum heap)

So, if they have child nodes that are equal, that means they can be duplicated.

Answer 3

Yes, but I would say no. For efficiency, they should not have different nodes with duplicate values ​​or they lose their purpose (you have to look for child nodes, etc.). However, you can create each node to contain a variable that declares how many copies of this value you have in your data.

Again, this is my opinion. If this is a bad way to do this, I would like someone to explain why. I just need to do some performance testing. If you store simple data types such as int, I would see that it is less efficient, but for larger objects that have identifiers, it was nice.