Python · A Level 7

Heaps, Tries and Disjoint Sets

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 20 marks. Total 30 marks.

Name

Class

Date

Mark / 30

Section A

Circle the letter of the correct answer. One mark each.

1In a min-heap, which item is always at the root?1
1. AThe largest item
2. BThe item added first
3. CThe item added most recently
4. DThe smallest item
2A heap is stored in a list with the first item at index 0. Where is the left child of the item at index 3?1
1. AIndex 1
2. BIndex 4
3. CIndex 6
4. DIndex 7
3What does 'sifting up' do?1
1. ARemoves the smallest item from the heap
2. BSorts the whole heap into ascending order
3. CSwaps a new item with its parent until the heap property holds
4. DMoves the root to the end of the list
4Why is a heap a better choice than a sorted list for a priority queue with many insertions?1
1. AA heap keeps every item in alphabetical order
2. BInserting into a heap is O(log n) but into a sorted list is O(n)
3. CA heap never needs to compare two items
4. DA heap can hold duplicates and a list cannot
5What is the time complexity of heap sort?1
1. AO(n log n)
2. BO(n)
3. CO(log n)
4. DO(n squared)
6What is a trie mainly used for?1
1. ASorting numbers into ascending order
2. BFinding all the words that begin with a given prefix
3. CDetecting cycles in a graph
4. DFinding the shortest path in a weighted graph
7A trie holds 50 000 words. About how many steps does it take to check whether the 4 letter word 'care' is in it?1
1. AAbout 16
2. BAbout 50 000
3. CAbout 4
4. DAbout 200 000
8What does path compression do in a union-find structure?1
1. APoints every item passed during a find straight at the root
2. BSorts the groups by size
3. CMerges two groups into one
4. DRemoves an item from its group
9A connected graph has 9 vertices. How many edges does a spanning tree of it have?1
1. A8
2. B9
3. C10
4. D18
10In Kruskal's algorithm, when is the next cheapest edge rejected?1
1. AWhen another edge has the same weight
2. BWhen it is the heaviest edge in the graph
3. CWhen both of its ends are already in the same group, so it would form a cycle
4. DWhen it touches the starting vertex

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

1StateState what is meant by the heap property of a min-heap.2
2ShowThe array shown holds a min-heap, with the first item at index 0. The value 3 is added to the heap and the heap property is restored by sifting up. Show the contents of the array after the value has been added and the heap property restored.4
```
index:  0  1  2  3  4  5
value:  2  5  4  9  7  8
```
3ExplainExplain why a binary heap is a better data structure than a sorted list for implementing a priority queue in which items are frequently added and removed.4
4WriteWrite a subprogram find(parent, x) for a disjoint set structure. The list parent holds the parent of each item, and an item that is the root of its group is its own parent. The subprogram must return the root of the group that x belongs to and must use path compression.4
5DiscussA web site offers search suggestions as a user types. Discuss whether a trie or a hash table would be the better structure to hold the dictionary of search terms.6

Mark scheme

Section A

1D2D3C4B5A6B7C8A9A10C

Section B

1 State what is meant by the heap property of a min-heap. 2

One mark for each of the following, to a maximum of 2.

Every parent is less than or equal to (smaller than) its children
So the smallest item is at the root

Model answer. In a min-heap every parent node is less than or equal to each of its children. This means that the smallest item in the heap is always at the root.

2 The array shown holds a min-heap, with the first item at index 0. The value 3 is added to the heap and the heap property is restored by sifting up. Show the contents of the array after the value has been added and the heap property restored. 4

One mark for each of the following, to a maximum of 4.

3 is added at the end of the array (index 6)
3 is compared with its parent 4 (index 2) and the two are swapped
3 is compared with its new parent 2 and no swap is needed
Final array is 2, 5, 3, 9, 7, 8, 4

Model answer. 3 is added at the end of the array, at index 6. Its parent is at index (6 - 1) // 2 = 2, which holds 4. Since 3 is less than 4 the two are swapped, so 3 is at index 2 and 4 is at index 6. The parent of index 2 is index 0, which holds 2. Since 2 is less than 3 no further swap is needed. The array is now 2, 5, 3, 9, 7, 8, 4.

3 Explain why a binary heap is a better data structure than a sorted list for implementing a priority queue in which items are frequently added and removed. 4

One mark for each of the following, to a maximum of 4.

Adding to a sorted list means shifting items along to make room, which is O(n)
Adding to a heap is O(log n) because the item only moves up one branch of the tree
Both can find the highest priority item quickly (it is at the front or the root)
A heap only keeps the items partly ordered, so it does less work than keeping every item in order

Model answer. In a sorted list a new item has to be put in its correct place, which means shifting every item after it along to make room. This takes O(n) time. In a heap the new item is added at the end and only moves up a single branch of the tree, which is at most log n levels, so adding is O(log n). Both structures can find the highest priority item immediately, since it is at the front of the list or the root of the heap. The heap is quicker overall because it only keeps the items partly ordered, instead of keeping all of them in order.

4 Write a subprogram find(parent, x) for a disjoint set structure. The list parent holds the parent of each item, and an item that is the root of its group is its own parent. The subprogram must return the root of the group that x belongs to and must use path compression. 4

One mark for each of the following, to a maximum of 4.

Subprogram takes parent and x and returns a root
Base case or loop end: x is its own parent so it is the root
Recursive call (or loop) on the parent of x
Sets parent[x] to the root found (path compression)

Model answer.

Python

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

parent = [1, 2, 3, 3]
print(find(parent, 0))
print(parent)

If x is its own parent it is the root and is returned. Otherwise find is called on the parent of x, and the root it returns is stored in parent[x], so that x now points straight at the root. This is path compression.

5 A web site offers search suggestions as a user types. Discuss whether a trie or a hash table would be the better structure to hold the dictionary of search terms. 6

One mark for each of the following, to a maximum of 6.

A trie can find every term beginning with the typed prefix by following the letters
A hash table can only look up a whole key, so it would have to check every key for a prefix match
The trie lookup time depends on the length of the prefix, not the number of terms
The trie returns the suggestions in alphabetical order without extra sorting
A trie uses more memory because it has a node for each letter, although shared prefixes are stored once
A reasoned conclusion: a trie is better for suggestions, a hash table for exact matches only

Model answer. A trie is the better choice. As the user types, the program follows the letters typed so far down the trie, and every term in the sub-tree below that point is a suggestion. The time taken depends on the length of the prefix and not on how many terms are stored, and the terms can be produced in alphabetical order without sorting them. A hash table can only look up a whole key, so to find the terms starting with a prefix it would have to check every key, which is O(n) for each keystroke. The trie does use more memory, because it needs a node for every letter, although terms that share a beginning share those nodes. A hash table would only be better if the program needed exact matches, so for search suggestions the trie should be used.