"Binary Heaps & Graphs as Data Structures" — Practice

Question 1

In a max-heap stored with 0-based indexing, what is the index of the parent of the element at index 9?

Accepted Answer

B

Question 2

What is the maximum number of edges in a simple directed graph on 6 vertices?

Accepted Answer

B

Question 3

What is the worst-case time to find the minimum element in a max-heap of n elements?

Accepted Answer

A

Question 4

Build a max-heap from the array [3, 9, 2, 1, 4, 5] using the linear-time method with 0-based indexing, showing each sift-down.

Accepted Answer

With n = 6, the last internal node is at floor of 6 over 2, minus 1 = 2. Sift down from index 2 to index 0.

Index 2 holds 2, with a left child at index 5 holding 5 and no right child, since index 6 is out of range. The largest is 5, and 5 exceeds 2, so swap.

Array: [3, 9, 5, 1, 4, 2]. The value 2 is now at index 5, a leaf, so this sift ends.

Index 1 holds 9, with children at indices 3 and 4 holding 1 and 4. The largest of the three is 9 itself, so nothing moves.

Index 0 holds 3, with children at indices 1 and 2 holding 9 and 5. The largest child is 9, which exceeds 3, so swap.

Array: [9, 3, 5, 1, 4, 2]. The value 3 is now at index 1.

Continue sifting 3 down. Its children at indices 3 and 4 hold 1 and 4. The largest is 4, which exceeds 3, so swap.

Array: [9, 4, 5, 1, 3, 2]. The value 3 is now at index 4, a leaf, so the sift ends.

The max-heap is [9, 4, 5, 1, 3, 2].

Verify: index 0 holds 9 with children 4 and 5, both smaller. Index 1 holds 4 with children 1 and 3, both smaller. Index 2 holds 5 with child 2, smaller. The property holds throughout. Indices 3, 4 and 5 were never sifted from, since they are the ceiling of 6 over 2 = 3 leaves.

Question 5

A graph has 1000 vertices and 3000 edges. Compare the space required by an adjacency matrix and an adjacency list, and state which operations each favours.

Accepted Answer

An adjacency matrix stores one entry per ordered pair, so it needs V squared = 1,000,000 entries regardless of how many edges exist. At one bit per entry that is 125 KB; at one byte per entry it is about 1 MB.

An adjacency list stores one node per directed edge plus one head pointer per vertex. For an undirected graph each edge appears twice, so the count is V plus 2E = 1000 plus 6000 = 7000 entries.

The list uses roughly 0.7 per cent as many entries as the matrix. The graph is sparse, with 3000 edges against a maximum of about 500,000, so almost the entire matrix is zeros.

As to operations, the matrix answers whether a specific edge exists in constant time by a single lookup, while the list must scan the neighbour list of one endpoint, costing time proportional to its degree.

The list lists a vertex's neighbours in degree time, while the matrix must scan an entire row of V entries even if the vertex has only two neighbours.

For this graph the average degree is 6, so listing neighbours costs 6 operations with a list against 1000 with a matrix. The list is clearly correct here, and the matrix would only be preferable if the edge count approached V squared.

Question 6

Explain why breadth-first search finds shortest paths in an unweighted graph but fails on a weighted one, with a concrete counterexample.

Accepted Answer

Breadth-first search maintains a queue and processes vertices strictly in the order they are discovered. Because a vertex is enqueued only when first reached, and because all vertices at distance k are enqueued before any at distance k plus 1, the search expands outward one layer at a time.

The first time a vertex is reached, it has therefore been reached by the fewest possible edges, and in an unweighted graph fewest edges means shortest path. Recording the discovering edge gives the shortest path tree directly, at a total cost of O(V + E).

The argument breaks on a weighted graph because fewest edges no longer means least weight.

Concretely, take vertices S, A and T with a direct edge from S to T of weight 100, an edge from S to A of weight 1, and an edge from A to T of weight 1.

Breadth-first search from S discovers T at distance 1 via the direct edge and finalises it, reporting a path of cost 100. The genuine shortest path goes S to A to T with total cost 2, but it uses two edges and is therefore discovered a layer later.

Dijkstra's algorithm fixes this by replacing the queue with a priority queue keyed on accumulated distance, so vertices are finalised in order of path weight rather than edge count. That change is exactly what the heap in this chapter provides, and it is why the two topics belong together.

Question 7

Prove that building a heap by sifting down costs O(n), and explain why building by repeated insertion does not.

Accepted Answer

The cost of sifting down from a node is proportional to that node's height, since the value can descend at most as far as the subtree below it extends. The tree's height does not bound each individual sift; the node's own height does.

In a heap of n nodes, the number of nodes at height h is at most n divided by 2 to the power h plus 1. Half the nodes are leaves with height 0, a quarter have height 1, an eighth have height 2, and exactly one node has the full height.

The total work is the sum over h from 0 to log n of (n over 2^(h+1)) times h.

Factoring out gives (n over 2) times the sum of h over 2^h.

That series converges: the sum of h over 2^h from h = 0 to infinity equals 2. So the total is bounded by n, giving O(n).

The intuition is that expensive sifts are rare. Only the root can cost the full log n, and the half of the array that is leaves costs nothing at all and is skipped by starting at the last internal node.

Repeated insertion is genuinely different. Each inserted element is appended at a leaf position and sifts up, and the path from a leaf to the root is the full height of the tree. Most insertions therefore happen at the deepest level, where the sift-up distance is longest, so the costs do not decay the way sift-down costs do. Summing log of i over i from 1 to n gives O(n log n), and the bound is tight.

Question 8

Prove that a directed graph is acyclic if and only if a depth-first search finds no back edge, and state how a topological order is then obtained.

Accepted Answer

First direction: if a back edge exists, the graph has a cycle. A back edge by definition leads from the vertex currently being explored to an ancestor that is still on the recursion stack. That ancestor reached the current vertex by a chain of tree edges, all directed downward. Following that chain and then the back edge returns to the starting vertex, so a directed cycle exists.

Second direction: if the graph has a cycle, a back edge must be found. Consider any cycle and let v be the first of its vertices discovered by the search. Since every other vertex on the cycle is reachable from v by directed edges within the cycle, and v is discovered first, all of them are discovered during v's exploration and become descendants of v in the depth-first tree. In particular the predecessor of v on the cycle is a descendant of v, and it is still on the stack when its edge back to v is examined, because v has not yet finished. That edge is therefore classified as a back edge.

The two directions together give the equivalence, and since the search costs O(V + E) this is the standard cycle-detection method.

When no back edge is found, the graph is a directed acyclic graph and a topological order exists. It is obtained by recording each vertex's finishing time and listing the vertices in decreasing order of that time. The correctness argument is that for any edge from u to v in an acyclic graph, u must finish after v, so u precedes v in the reversed finishing order.

Question 9

A simple undirected graph has 12 vertices and 20 edges. Prove it must contain a cycle, and determine the minimum number of independent cycles.

Accepted Answer

A graph is acyclic exactly when each of its connected components is a tree. A tree on k vertices has exactly k minus 1 edges.

Suppose the graph is acyclic with C components, of sizes k1 through kC summing to 12. The total edge count would be the sum of (ki minus 1), which equals 12 minus C.

Since C is at least 1, the maximum edge count for an acyclic graph on 12 vertices is 12 minus 1 = 11, achieved when the graph is a single spanning tree.

The graph has 20 edges, which exceeds 11, so it cannot be acyclic and must contain a cycle.

For the number of independent cycles, use the cyclomatic number, which counts the edges that must be removed to leave a spanning forest.

Independent cycles = E minus V plus C = 20 minus 12 plus C = 8 plus C.

The minimum occurs when C is as small as possible. Since the graph could be connected, C can be 1, giving a minimum of 9 independent cycles.

As a check, a connected graph on 12 vertices has a spanning tree with 11 edges, leaving 20 minus 11 = 9 extra edges, and each extra edge closes exactly one independent cycle. The two computations agree.

Note that more components would give more independent cycles, not fewer, because each component needs its own spanning tree and therefore leaves more edges over.

Practice — "Binary Heaps & Graphs as Data Structures"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities