javabinary-treeheapsortmin-heapmax-heap

Can max/min heap trees contain duplicate values?


I'm wondering if a max or min heap tree is allowed to have duplicate values? I've been unsuccessful in trying to find information regarding this with online resources alone.


Solution

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

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