The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees $$(MSTs)$$ of $$G$$ is/are TRUE?

$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ If $$e$$ is the lightest edge of some cycle in $$G,$$ then every $$MST$$ of $$G$$
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$includes $$e$$
$$\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ If $$e$$ is the heaviest edge of some cycle in $$G,$$ then every $$MST$$ of $$G$$
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$excludes $$e$$

Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given by the entry $${W_{ij}}$$ in the matrix $$W.$$ $$$W = \left[ {\matrix{ 0 & 2 & 8 & 5 \cr 2 & 0 & 5 & 8 \cr 8 & 5 & 0 & X \cr 5 & 8 & X & 0 \cr } } \right]$$$

The largest possible integer value of $$x,$$ for which at least one shortest path between some pair of vertices will contain the edge with weight $$x$$ is _________________.

An operator $$delete(i)$$ for a binary heap data structure is to be designed to delete the item in the $$i$$-th node. Assume that the heap is implemented in an array and i refers to the $$i$$-th index of the array. If the heap tree has depth $$d$$ (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?