Question

explain briefly

(d) (4%) What kind of heaps is required in heap sort with non-decreasing order? Why? (e) (4%) Consider the single source all destinations problem. Explain why it is required that the graph have no cycles of negative length when negative edge lengths are permitted. (f) (6%) Consider the set representation using trees. If the sets being represented are pairwise disjoint, explain what the collapsing rule is. What scenario is more beneficial for the find operation applying collapsing rule? Why?

Answer 1

Answer d - For the heaps of non-decreasing order the max-heap is required, because of the following reason:-

=> The key represented by the root node which must be the greatest of all the keys among the children

Answer e- Considering the single source all destination problem the algorithm only says to not have a negative cycle. For the negative length, the algorithm is not correct because the non-negativity is the proof for the single-source all destination problem. The algorithm will surely stop after iterations n-1 for n vertices.

For the negative cycle implementable form, as there will be no shortest path from source to the vertex on the given cycle, hence solution can be obtained for this going around cycle on every path although this will take additional time.

Answer f- Suppose the node is n on the given path say p upto the root and

parent[p] != root(p), so this the collapsing rule for the trees formed by the adjoint sets then the parent[n] set to the root(p)

For the application of the find() operation

The compression should be done for that to find out the root because if we make the found root the parent of the element so there will be no need to traverse again from the element to find out the root.

//I TRIED TO EXPLAIN AS BRIEFLY AS POSSIBLE AS YOU MENTIONED ABOVE IF STILL SOME QUERIES PLEASE REVERT IN THE COMMENT SECTION FOR FURTHER HELP...............HAPPY TO HELP!!!!!!!!!!!