adt.quakeheap.QuakeHeap

   1 package adt.quakeheap;
   2 
   3 import java.util.ArrayList;
   4 import java.util.List;
   5 import java.util.Random;
   6 
   7 import adt.tournament.Node;
   8 import adt.tournament.TournamentTree;
   9 
  10 
  11 /**
  12  * @author Sebastian Kuerten (sebastian.kuerten@fu-berlin.de)
  13  * 
  14  */
  15 public class QuakeHeap
  16 {
  17     int numberOfElements = 0;
  18     List<List<TournamentTree>> T = new ArrayList<List<TournamentTree>>();
  19     List<Integer> n = new ArrayList<Integer>();
  20 
  21     public QuakeHeap()
  22     {
  23         T.add(new ArrayList<TournamentTree>());
  24         n.add(0);
  25     }
  26 
  27     public Node insert(int value)
  28     {
  29         numberOfElements += 1;
  30         TournamentTree tree = new TournamentTree(value);
  31         Node leaf = tree.getRoot();
  32         T.get(0).add(tree);
  33         n.set(0, n.get(0) + 1);
  34         return leaf;
  35     }
  36 
  37     public void decreaseKey(Node leaf, int key)
  38     {
  39         Node node = leaf.getHighestEqualNode();
  40         if (node.isRoot()) {
  41             node.setValue(key);
  42         } else {
  43             TournamentTree cut = TournamentTree.cut(node);
  44             leaf.setValue(key);
  45             int height = cut.getHeight();
  46             // height is smaller or equal to the highest tree
  47             // thus it is safe to assume that T.get(height) exists.
  48             T.get(height).add(cut);
  49         }
  50     }
  51 
  52     /**
  53      * Retrieve the minimum of the stored values.
  54      * 
  55      * @return the minimal value contained in the heap.
  56      */
  57     public int deleteMin()
  58     {
  59         // get a list of all trees
  60         List<TournamentTree> allTrees = getAllTrees();
  61 
  62         // we need at least one tree
  63         if (allTrees.size() == 0) {
  64             // this is an error
  65             return Integer.MAX_VALUE;
  66         }
  67 
  68         // since we will delete an element, decrease element count.
  69         numberOfElements -= 1;
  70 
  71         // STEP 1: find minimum
  72         TournamentTree minTree = allTrees.get(0);
  73         for (TournamentTree tree : allTrees) {
  74             if (tree.getRootValue() < minTree.getRootValue()) {
  75                 minTree = tree;
  76             }
  77         }
  78 
  79         // STEP 2: delete path for element
  80         // minTree is the tree with the smallest element now
  81         int height = minTree.getHeight();
  82         // remove tree from T
  83         T.get(height).remove(minTree);
  84         // delete the path
  85         Node minRoot = minTree.getRoot();
  86         List<Node> newRoots = minRoot.collectDifferentDescandents();
  87         // for each of the nodes disconnected along the path
  88         for (Node newRoot : newRoots) {
  89             // create a new tree and insert to T
  90             TournamentTree tree = new TournamentTree(newRoot);
  91             T.get(tree.getHeight()).add(tree);
  92             // heights remain the same for the disconnected subtrees
  93         }
  94         // adjust n
  95         for (int i = 0; i <= height; i++) {
  96             n.set(i, n.get(i) - 1);
  97         }
  98         // clean arrays (remove tail elements if not in use anymore)
  99         cleanUpArrays();
 100 
 101         // STEP 3: consolidate
 102         for (int i = 0; i < T.size(); i++) {
 103             List<TournamentTree> listI = T.get(i);
 104             while (listI.size() >= 2) {
 105                 TournamentTree t1 = listI.remove(listI.size() - 1);
 106                 TournamentTree t2 = listI.remove(listI.size() - 1);
 107                 TournamentTree linked = t1.link(t2);
 108                 // we might have to use a previously empty field of the array,
 109                 // so make sure it exists
 110                 ensureSizeOfArrays(i + 2);
 111                 T.get(i + 1).add(linked);
 112                 n.set(i + 1, n.get(i + 1) + 1);
 113             }
 114         }
 115 
 116         // STEP 4: quake
 117         // check invariant: n[i+1] <= 3/4 * n[i]
 118         for (int i = 0; i < T.size() - 1; i++) {
 119             boolean holds = n.get(i + 1) <= 3.0 / 4 * n.get(i);
 120             if (holds) {
 121                 continue;
 122             }
 123             System.out.println("not ok on level: " + i);
 124             System.out.println("# elements: " + getNumberOfElements());
 125             // execute quake on layers i+1 and upwards
 126             for (int k = i + 1; k < T.size(); k++) {
 127                 quake(k, i);
 128             }
 129             cleanUpArrays();
 130             break;
 131         }
 132 
 133         // finally return the minimum value
 134         return minTree.getRootValue();
 135     }
 136 
 137     private void quake(int k, int keep)
 138     {
 139         List<TournamentTree> trees = T.get(k);
 140         for (TournamentTree tree : trees) {
 141             List<Node> levelNodes = tree.getNodesOnLevel(keep);
 142             for (Node node :levelNodes){
 143                 TournamentTree newTree = new TournamentTree(node);
 144                 T.get(keep).add(newTree);
 145             }
 146         }
 147         // reset values in n, T
 148         n.set(k, 0);
 149         T.set(k, new ArrayList<TournamentTree>());
 150     }
 151 
 152     /*
 153      * Since we are using dynamically adjusting arrays for T and n, we have to
 154      * make sure at certain situations that the sizes of these arrays are at
 155      * least 'size'.
 156      */
 157     private void ensureSizeOfArrays(int size)
 158     {
 159         int missing = size - T.size();
 160         for (int i = 0; i < missing; i++) {
 161             T.add(new ArrayList<TournamentTree>());
 162             n.add(0);
 163         }
 164     }
 165 
 166     /*
 167      * After deleting a path from the tallest tree t with height k, it might
 168      * occur iff t was the only tree of height n, that the value for n[k]
 169      * becomes 0. In that case we want to reduce T's and n's size by one to keep
 170      * our arrays smart and being able to use the length of them as
 171      * loop-iterations boundaries.
 172      * 
 173      * Note that the deletion of the last element of n might 'reveal' additional
 174      * trailing zeros that will be deleted, too.
 175      */
 176     private void cleanUpArrays()
 177     {
 178         // loop until the last element of T is non-empty
 179         while (true) {
 180             int last = T.size() - 1;
 181             if (last == 0) {
 182                 // don't remove the last entry, even if it's empty
 183                 break;
 184             }
 185             List<TournamentTree> trees = T.get(last);
 186             if (trees.size() == 0) {
 187                 T.remove(last);
 188                 if (n.get(last) != 0) {
 189                     System.out.println(
 190                             "clean up error: last should be 0, but it is "
 191                                     + n.get(last));
 192                 }
 193                 n.remove(last);
 194                 // removed last because it was 0
 195                 // go on to make sure the last element is not empty
 196                 continue;
 197             }
 198             break;
 199         }
 200     }
 201 
 202     /*
 203      * Retrieve a list of all tournament trees this quake heap consists of.
 204      */
 205     public List<TournamentTree> getAllTrees()
 206     {
 207         // iterate all tree lists
 208         List<TournamentTree> trees = new ArrayList<TournamentTree>();
 209         for (List<TournamentTree> list : T) {
 210             // and add them to our result list
 211             trees.addAll(list);
 212         }
 213         return trees;
 214     }
 215 
 216     /**
 217      * Does this Quake heap contain any elements?
 218      * 
 219      * @return whether this quake heap contains any elements at all.
 220      */
 221     public boolean hasElements()
 222     {
 223         return getNumberOfElements() > 0;
 224     }
 225 
 226     /**
 227      * Get the number of elements within this quake heap.
 228      * 
 229      * @return the number of elements.
 230      */
 231     public int getNumberOfElements()
 232     {
 233         return numberOfElements;
 234     }
 235 
 236     /**
 237      * Get a random tree included in the quake heap. For testing only.
 238      * 
 239      * @param random
 240      *            a random number generator to use
 241      * @return a randomly selected tree.
 242      */
 243     public TournamentTree getRandomTree(Random random)
 244     {
 245         List<TournamentTree> allTrees = getAllTrees();
 246         int index = random.nextInt(allTrees.size());
 247         return allTrees.get(index);
 248     }
 249 
 250     /**
 251      * Get a randomly selected leaf of this quake heap. For testing only.
 252      * 
 253      * @param random
 254      *            a random number generator to use.
 255      * @return a randomly selected leaf.
 256      */
 257     public Node getRandomLeaf(Random random)
 258     {
 259         TournamentTree tree = getRandomTree(random);
 260         return tree.getRandomLeaf(random);
 261     }
 262 }