Menu
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.
529
First, we can always have duplicate values in a heap — there's no restriction against that. Second, a heap doesn't follow the rules of a binary search tree; unlike binary search trees, the left node does not have to be smaller than the right node!
In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed.
In a Max-Heap the key present at the root node must be greater than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Max-Heap the maximum key element present at the root.
Min-Heap − Where the value of the root node is less than or equal to either of its children. Max-Heap − Where the value of the root node is greater than or equal to either of its children. Both trees are constructed using the same input and order of arrival.
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.
78
Yes they can have duplicates. From wikipedia definition of Heap:
Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap)
So if they have children nodes that are equal means that they can have duplicated.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
