What is the difference between min heap and max heap? is it possible to shuffle the elements during insertion time? If so then how come the complexity is logn
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The difference between min and max heap is in the invariant holding before and after any insertion or deletion. Namely in a max heap the keys of the son's of a node are always smaller then the node itself (i.e. biggest key is root). In a min-heap the son's keys are always bigger (i.e. smallest key is root).
When inserting a new node with key x you insert it in the first empty leaf of the structure (usually the leftmost leaf). this will probably invalidate the invariant, therefore we need now to adjust the heap. just compare the newly inserted node's key with its parent recursively and swap them if the heap invariant doesn't hold. Repeat the adjusting step until the father is smaller/bigger than it's son [minheap/maxheap]. The complexity of an insertion is log(n) because the heap always has a height of log(n) and the adjusting part of the insertion (which is also the most expensive) starts from a leaf (the node we just inserted) and brings it (in the worst case) to the root.
for more material see: https://en.wikipedia.org/wiki/Min-max_heap
