Problem

Give an efficient implementation of an operation PRUNE(H, r), which deletes min(r, n[H]) nodes from H. Which nodes are deleted should be arbitrary. Analyze the running time of your implementation.

Solution

The basic idea is to maintain a doubly-linked list of pointers to leaf nodes. A global pointer to access this list is also required in the heap structure. Only leaf nodes are pruned. If pruning converts some parent nodes into leaf nodes, they are added to the leaf list as well. Also, when a node losses its second child during the pruning process, cascading cuts will occur.

Algorithms

A suggested algorithm for pruning is given below. We assume that r < n, otherwise the entire heap should be deleted without the need for pruning.

PRUNE(H, r) {
   if (r == 0)
      return
   endif
   x = leaf[H] // Get a node from the main leaf pointer.
   if (x == min[H])
      x = x.right // Skip min node.
   endif
   y = PARENT(x)
   if (y == NIL)
      We are in the root list.
      Remove node x from the root list
   else 
      Remove x from the child list of y.
      Decrement the rank of y.
      CASCADING-CUT(H, y)
      (Note: CUT procedure will have to be modified to add items to 
      the leaf list if all the children are cut.)
   endif
   leaf[H] = leaf[H].next
   free(x)
   PRUNE(H, r-1)
   }

Analysis

Simple operations in individual procedures that must maintain the leaf list all cost O(1) time.  These operations are:

• INSERT - charged O(1) for adding a node to the leaf list.
  
• UNION - charged O(1) for combining the two leaf lists
  
• DECREASE_KEY - recall that a DECREASE_KEY is responsible for the costs associated with two nodes - the node X where the DECREASE_KEY is being done, and the node Y where the cascading cut ends.  When X is placed into the root list, nothing new happens to it in so far as the leaf list is concerned.  But, when Y loses its second child, and goes to the root list, it may also be that Y becomes a leaf, in which case it is added to the leaf list and the DECREASE_KEY responsible for Y is charged O(1).
  
• DELETE_MIN - when two nodes of rank zero are linked, one leaf is removed from the leaf list.  Whatever operation is charged for the link is also charged for that leaf list removal.  Interestingly, say if Y becomes the child of X, then the operation charged is one responsible for Y (for instance, the INSERT of Y) and yet that "Y" operation is the one paying for X to be removed from the leaf list.

Aside from the leaf list maintenance considerations, the entire pruning process will cost O(r) plus the cost for the resulting cascading cuts that might occur. How can we assign charges that will leave us with an amortized cost of O(1) for PRUNE? We cannot charge the pruning process anything or we end up with the process being O(r) which is still O(n).

Thus, we charge the INSERT operation for the cost of pruning the node that was INSERTed. That is, to prune a node X, we charge the INSERT that placed X into the Fibonacci heap. A node can only be pruned once, so its corresponding INSERT can only be charged once for this.  Further, since the prune of X may result in a cascading cut, the INSERT of X also becomes responsible for the node Y where that cascading cut ends.  That means that the INSERT of X will pay for:  a subsequent cut of Y, and later, a link of Y, and also an O(1) if the node that becomes Y's parent in a link, had been in the leaf list.  But these are all O(1) operations and the INSERT of X can only be charged once each in this fashion.

Note also that when the pruning operation results in the cascading cut of a node X, we charge the operation who is responsible for X.  That is the operation charged for the operation whose cascading cut stopped at X.  That will be either a DECREASE-KEY or as described above, the INSERT of the node the prune of which caused a cascading cut that stopped at X.   So, in summary, for cascading cuts, either DECREASE_KEYS or INSERTS will be charged, but they are only charged O(1) in this fashion and only one time, so their total amortized costs are O(1).

Finally, the prune operation itself is charged just O(1) - bascially for the test if r==0 in the first line of the algorithm.