Hi I have this question that in the heap data structure , a left child can be more than a right child in its own level ? I mean that consider these three numbers 9,5,8 and I want to make a max-heap data structure so the root will be 9 and is it true that 8 be its left child and 5 be its right child? please help me thanks
A:
That doesn't matter. A node in a max-heap must have children that are lower, and a node in a min-heap must have children that are greater. Those are the only requirements.
Daniel Egeberg
2010-06-25 07:11:18
so there is no rule for how we set the left and right child of a parent?because heap is nearly complete binary tree and I think it was a rule in the binary tree that left child should be less that right child!and I think for my above example I should write "root:9" and "leftChild:5" and "rightChild:8",isn't?
2010-06-25 07:16:23
The way you would typically build a max heap is to start in the middle of the array downto the first element and recursively let each node sift down through the tree by exchanging nodes. This can be done in O(n) time. It isn't a binary search tree, so there is no particular relation between sibling nodes besides the fact that they're both smaller (or greater in the case of a min-heap) than their parent.
Daniel Egeberg
2010-06-25 07:25:34
aha and if we want to search a key in this data structure we don't need to make it as a binary search tree ?
2010-06-25 07:45:20
Heaps aren't really suited for searching. Searching in a heap is a O(n) operation, so it's no better than an array or list. If you want to search then a binary search tree would be better because you can search in O(h) time (where h is the height). For instance, a red-black tree has height O(lg n), so you can search in logarithmic time.
Daniel Egeberg
2010-06-25 07:55:18
for example if I want to search for minimum in the Max heap so I need my tree to be like a binary search tree?
2010-06-25 08:10:36
If you need to find minimum elements, using a min-heap would be better as it would be the root. What exactly is it you're trying to do? Why do you want to use a heap? In general, if it's searching you need the a heap is not the appropriate data structure.
Daniel Egeberg
2010-06-25 08:28:24