Consider a heap ‘H’. Each key in a heap is randomly increased or decreased by 1. Then we can restore the heap property on H in linear time O(n). The random choices are independent.
True or false??
---------------------------------------------
i dun think we need even O(n) time to restore heap property
take these heaps.first one is unmodified , following min heap property,then second one after inc or dec by 1
to rstore min heap property in second heap,we just need to call min-heapify on the root which will take just logn time.
i dun think there is a need to build the heap again by calling build-heap() function which takes O(n) time and then calling min-heapify().
please verify this