CS2040S- Recitation 9 Solved

Goals:

•    Apply ideas from Union-Find

•    Explore more heap variants and their properties

•    Reinforce algorithm design principles

Problem 1.              A whole lot of work to do....

Suppose you have a huge amount of work to do. To keep track of the n tasks, you have a big array W where W[j] = 0 means that task j has not yet been completed, and W[j] = 1 implies that task j has been completed.

0
0
1
0
0
1
1
1
1
1
0
0
                                              0        1        2        3        4        5        6        7        8        9      10     11

Figure 1: An example of W.

In order to help coordinate getting all the work done, you want to implement a data structure that implements the following three operations:

Operation
Behaviour
lookup(j)
returns the value W[j].
mark(j)
marks task j as completed, i.e., sets W[j] = 1.
nextTask(j)
returns the next task ≥ j that is not yet completed, i.e., the next index j ≥ 0 where W[j] = 0.
For example, for the array above (Figure 1), lookup(2) returns 1, mark(4) would change the zero to a one, and nextTask(6) would return 10.

The simplest solution, of course, is just to use the array. In that case, it is easy to implement the lookup and mark operations in O(1) time, but the nextTask operation may take Ω(n) time.

The goal in this problem is to develop data structures that provide different trade-offs in performance. For all versions, we want lookup to complete in O(1) time.

Problem 1.a. Design a data structure where the mark and nextTask operations complete in O(logn) time, worst-case.

Problem 1.b. Design a data structure where the mark operation runs in O(logn) amortized time and nextTask operation runs in O(1) time, worst-case.

Problem 1.c. Design a data structure where the mark operation runs in worst-case O(1) time and nextTask operation runs in O(α(n)) amortized time (where α(n) refers to the time complexity of the inverse Ackermann function, i.e., the amortized time for executing n operations on a unionfind data structure).

Problem 2.             Communist Data Structures

In this problem we will build a new type of mergeable Max-Heap. It is often useful to be able to merge data structures. For example, they can be used to build divide-and-conquer algorithms, they can be used more easily in augmenting trees, etc.

Let us define the following terms:

Term
Definition
right spine
The sequence of nodes traversed in a tree if you start at a node and always go right until you find a node with no right child (which may not be a leaf).
rightRank
The number of nodes along a right spine.
LEFTIST property
The property a tree satisfies if, for every node that has two children L and R, rightRank(L) >= rightRank(R).
LEFTIST (Max) HEAP
A tree that satisfies both the (Max) Heap order property and the LEFTIST property.
 

Figure 2: Example of a LEFTIST HEAP, where the rightRank for each node is labelled next to it.

Problem 2.a.               What is the maximum height/depth of a LEFTIST HEAP?

Problem 2.b.                 What is the maximum rightRank of a LEFTIST HEAP containing n nodes?

Problem 2.c.    Suppose you want to add a node to a LEFTIST HEAP. Where would be a good place to insert it? What is the maximum cost?

Hints: Think recursively! Where is an efficient place to insert it? Realise also you can always swap the left and right subtrees of a node if it does not satisfy the LEFTIST property.

Problem 2.d. Now come up with an algorithm for merging two LEFTIST HEAPs together. What is the running time?

Hint: Apply the same idea from part b.

Problem 2.e.               How would you implement extractMax in a LEFTIST HEAP?

Problem 2.f. How would you implement delete (and decreaseKey) efficiently in such a LEFTIST HEAP?