Selected solutions for HW #4

#2a. (Weiss, 6.14) If a d-heap is stored as
an array, for an entry located at position i,
where are the parents and children?


Assuming that the root is at position 1 in
the array (as are binary heaps in the book),
then the formulas are:

parent of i is floor( (i+d-2) / d )
children of i are:
  d*i - d + 2 (inclusive) through d*i + 1 (inclusive)

It's easy to see the pattern by looking at d-heaps for
small values of d.  As an example, consider the first
few nodes of a d-heap, where d = 4.

i   children of i
1   2 3 4 5
2   6 7 8 9
3   10 11 12 13
4   14 15 16 17
5   18 19 20 21


#2b. (Weiss, 6.17a) Suppose that binary heaps are
represented by explicit links.  Consider the problem
of merging binary heap lhs and rhs.  Assuming both
heaps are full complete trees, containing 2^l - 1 and
2^r - 1 nodes, respectively.  Give an O(log N)
algorithm to merge two heaps if l = r.


Recall what happens in a deleteMin operation.
The root of the tree is "removed" and is replaced
by the last element in the heap.  Before the
last element was promoted to the root, notice that
the rootless heap is really just two heaps.

We have a similar situation when we try to merge
two full complete trees of height l.  Think of
the two heaps as the result just after a deleteMin
operation.  As in the deleteMin operation, we
promote the last element of, say, the right heap
to the root and make the remainder of the right
heap the right child of the root.  We also make
the left heap the left child of the root.  All of
this can be done in O(1) time.

At this point, the heap has the correct structure,
but it might not have the heap order property.
As in deleteMin, we need to percolateDown the
root element.  This takes O(log N) time.

So, the total time to for the merge is O(log N).

[Thought question: why was it necessary in this
problem to have the heaps be represented by
explicit links instead of two arrays?]


#4 (Weiss, 9.7a)
Give an example where Dijkstra's algorithm gives the
wrong answer in the prescence of a negative edge but
no negative-cost cycle.

The simplest example consists of three nodes (call
them a, b, and c) with edges and weights as follows:

a->b  2
a->c  1
b->c -5

If we start Dijkstra's algorithm from node a (that is,
we are trying to find the shortest path from a to
all other nodes) the algorithm will add a to the
set of known vertices (i.e., delete it from the priority
queue) and update the distances to b (2) and c (1)
in the priority queue.

Since c has the smallest distance in the priority queue,
it is deleted from the priority queue, but no nodes
are adjacent to it, so no nodes have their distances
updated.

The final distances from a will be:
a: 0
b: 2
c: 1

However, the shortest distance from a to c is via b
(-3 total cost).

Note that the following graph (again, three nodes a, b, and c)
is NOT an example that the problem asks for:

a->b  1
a->c  2
b->c -5

In this case, Dijkstra's algorithm will correctly compute
the shortest distances (a: 0, b: 1, c: -4) because b will be
deleted from the priority queue before c, and since c
is adjacent to b, its distance will be updated (by
decreasing it to -4 from 2) before being deleted from
the priority queue.