We can build a heap by inserting n elements using HEAPIFY-UP. The runtime of this procedure can be stated as (nlogn). The runtime of a call to HEAPIFY-UP is not (logn) because the call could be faster (e.g., O(1) if we insert something that will be the max of the heap). HEAPSORT is an asymptotically optimal sorting algorithm. In a min-heap, the vargest element is always at a leaf. The second smallest element in a heap is always a child of the root. The adjacency list representation of a graph has an asymptotically smaller space complexity than the adjacency matrix representation of the same graph. An undirected graph is a tree if and only if it contains exactly n1 edges. Testing whether a specific edge (u,v) exists using an adjacency matrix takes O(m) time, in the worst case. If a graph G is not connected, then it must be the case that n>m. If you want to represent a weighted graph, you have to use an adjacency matrix - there's no way to store the weights in an adjacency list