Suppose that you insert 33 into the following heap. What does the heap look like after the insertion, and after restoring it to a heap using reheapUp? Note that only the priorities are shown. Do not worry about additional information.
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
Suppose that you remove the smallest value from the following heap. What does the heap look like after the removal, and after restoring it to a heap using reheapDown?
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
How long does it take, in terms of n, to remove the smallest thing from a heap? The answer only needs to be correct to within a constant factor.
Dijkstra's shortest distance algorithm performs a sequence of basic update operations, where one basic update consists of finding a vertex u, marking u done, and then updating the status and other information of all vertices that are adjacent to u. If there are n vertices, about how many basic update operations does Dijkstra's algorithm do, in the worst case?
Suppose that you use the merge/together algorithm discussed in class to manage connections in a graph. Show how the boss array changes as each of the following operations are done. Use the algorithm that does not do either of the improvements -- the basic algorithm. Use the variant where merge always makes its first parameter's leader the new boss of the second parameter's leader.
In the diagram, the merge function is abbreviated m. So, for example m(2,4) indicates that you should merge 2 and 4.
i boss[i] i boss[i] i boss[i] i boss[i]
1 1 1 ____ 1 ____ 1 ____
2 2 2 ____ 2 ____ 2 ____
m(1,5) m(5,2) m(5,4)
3 3 --------> 3 ____ --------> 3 ____ --------> 3 ____
4 4 4 ____ 4 ____ 4 ____
5 5 5 ____ 5 ____ 5 ____
Suppose that a linked list is built from list cells, where each cell has the following type.
struct ListCell
{
ListCell* next;
int item;
ListCell(int i, ListCell* n)
{
next = n;
item = i;
}
};
Write a function called copylist that will produce a copy
of a linked list. The copy must be built out of new list cells.
ListCell* copylist(const ListCell* L)
Using the type ListCell from the preceding problem, write a function called take such that take(n,L) returns the length n prefix of list L, using new list cells. This function must not modify list L. If L has fewer than n members, then take(n, L) should produce a copy of L.
ListCell* take(int n, const ListCell* L)