mev-4.0.01/source/org/tigr/microarray/mev/motif/Heap.java

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2 Copyright @ 1999-2005, The Institute for Genomic Research (TIGR).
2 26 Feb 07 jari 3 All rights reserved.
2 26 Feb 07 jari 4 */
2 26 Feb 07 jari 5 /*
2 26 Feb 07 jari 6  * $RCSfile: Heap.java,v $
2 26 Feb 07 jari 7  * $Revision: 1.3 $
2 26 Feb 07 jari 8  * $Date: 2005/03/10 15:40:35 $
2 26 Feb 07 jari 9  * $Author: braistedj $
2 26 Feb 07 jari 10  * $State: Exp $
2 26 Feb 07 jari 11  */
2 26 Feb 07 jari 12 package org.tigr.microarray.mev.motif;
2 26 Feb 07 jari 13
2 26 Feb 07 jari 14 public class Heap {
2 26 Feb 07 jari 15     int N;           /* max number of items in heap */
2 26 Feb 07 jari 16     int n;           /* number of items in heap */
2 26 Feb 07 jari 17     int d;           /* base of heap */
2 26 Feb 07 jari 18     int[] h;         /* {h[1],...,h[n]} is set of items */
2 26 Feb 07 jari 19     int[] pos;           /* pos[i] gives position of i in h */
2 26 Feb 07 jari 20     int[] kvec;          /* kvec[i] is key of item i */
2 26 Feb 07 jari 21     
2 26 Feb 07 jari 22     Heap(int N,int D) {
2 26 Feb 07 jari 23   this.N = N;
2 26 Feb 07 jari 24   d = D;
2 26 Feb 07 jari 25   n = 0;
2 26 Feb 07 jari 26   h = new int[N];
2 26 Feb 07 jari 27   pos = new int[N];
2 26 Feb 07 jari 28   kvec=new int[N];
2 26 Feb 07 jari 29   for (int i=0; i<N; i++) pos[i] = 0;
2 26 Feb 07 jari 30     }
2 26 Feb 07 jari 31     /* insert item i with specified key */
2 26 Feb 07 jari 32     public void insrtHeap(int i,double k) {
2 26 Feb 07 jari 33   if (i<0) System.out.println("fatal! item to insert is < 0");
2 26 Feb 07 jari 34   if (pos[i]!=-1) rmHeap(i);
2 26 Feb 07 jari 35   kvec[i] = (int)k;
2 26 Feb 07 jari 36   n++;
2 26 Feb 07 jari 37   siftupHeap(i,(int)n);
2 26 Feb 07 jari 38     }
2 26 Feb 07 jari 39     
2 26 Feb 07 jari 40     /* Remove item i from heap. */
2 26 Feb 07 jari 41     int rmHeap(int i) {
2 26 Feb 07 jari 42   int j;
2 26 Feb 07 jari 43   if (pos[i]==-1) return -1;
2 26 Feb 07 jari 44   j = h[(int)n--];
2 26 Feb 07 jari 45   if (i != j && kvec[(int)j] <= kvec[i]) siftupHeap((int)j,(int)pos[i]);
2 26 Feb 07 jari 46   else if (i != j && kvec[(int)j]>kvec[i]) siftdownHeap((int)j,(int)pos[(int)i]);
2 26 Feb 07 jari 47   pos[i] = -1;
2 26 Feb 07 jari 48   return i;
2 26 Feb 07 jari 49     }
2 26 Feb 07 jari 50     
2 26 Feb 07 jari 51     /* delete and return item with smallest key */
2 26 Feb 07 jari 52     public int delminHeap() {
2 26 Feb 07 jari 53   int i;
2 26 Feb 07 jari 54   if (n == 0) return 0;
2 26 Feb 07 jari 55   i = h[0];
2 26 Feb 07 jari 56   rmHeap((int)h[0]);
2 26 Feb 07 jari 57   return i;
2 26 Feb 07 jari 58     }
2 26 Feb 07 jari 59     
2 26 Feb 07 jari 60     /* Shift i up from position x to restore heap order.*/
2 26 Feb 07 jari 61     void siftupHeap(int i ,int x) {
2 26 Feb 07 jari 62   int px = pHeap(x);
2 26 Feb 07 jari 63   while (x > 0 && kvec[(int)h[(int)px]]>kvec[i]) {
2 26 Feb 07 jari 64       h[(int)x] = h[(int)px];
2 26 Feb 07 jari 65       pos[(int)h[(int)x]] = x;
2 26 Feb 07 jari 66       x = (int)px;
2 26 Feb 07 jari 67       px = pHeap(x);
2 26 Feb 07 jari 68   }
2 26 Feb 07 jari 69   h[x] = i;
2 26 Feb 07 jari 70   pos[i] = x;
2 26 Feb 07 jari 71     }
2 26 Feb 07 jari 72     
2 26 Feb 07 jari 73     public int pHeap(int x) {
2 26 Feb 07 jari 74   return((x+(d-2))/d);
2 26 Feb 07 jari 75     }
2 26 Feb 07 jari 76     
2 26 Feb 07 jari 77     /* Shift i down from position x to restore heap order.*/
2 26 Feb 07 jari 78     public void siftdownHeap(int i,int x) {
2 26 Feb 07 jari 79   int cx = minchildHeap(x);
2 26 Feb 07 jari 80   while (cx != -1 && kvec[(int)h[(int)cx]] < kvec[i]) {
2 26 Feb 07 jari 81       h[x] = h[(int)cx];
2 26 Feb 07 jari 82       pos[(int)h[x]] = x;
2 26 Feb 07 jari 83       x = (int)cx;
2 26 Feb 07 jari 84       cx = minchildHeap(x);
2 26 Feb 07 jari 85   }
2 26 Feb 07 jari 86   h[x] = i;
2 26 Feb 07 jari 87   pos[i] = x;
2 26 Feb 07 jari 88     }
2 26 Feb 07 jari 89     
2 26 Feb 07 jari 90     /* Return the position of the child of the item at position x
2 26 Feb 07 jari 91        having minimum key. */
2 26 Feb 07 jari 92     int minchildHeap(int x) {
2 26 Feb 07 jari 93   int y, minc;
2 26 Feb 07 jari 94   if ((minc = leftHeap(x)) > n) return -1;
2 26 Feb 07 jari 95   for (y = minc + 1; y <= rightHeap(x) && y <= n; y++) {
2 26 Feb 07 jari 96       if (kvec[(int)h[(int)y]] < kvec[(int)h[(int)minc]]) minc = y;
2 26 Feb 07 jari 97   }
2 26 Feb 07 jari 98   return minc;
2 26 Feb 07 jari 99     }
2 26 Feb 07 jari 100     
2 26 Feb 07 jari 101     public int leftHeap(int x) {
2 26 Feb 07 jari 102   return(d*((x)-1)+2);
2 26 Feb 07 jari 103     }
2 26 Feb 07 jari 104     
2 26 Feb 07 jari 105     public int rightHeap(int x) {
2 26 Feb 07 jari 106   return(d*(x)+1);
2 26 Feb 07 jari 107     }
2 26 Feb 07 jari 108 }

Generated on Thu Jul 20 09:30:04 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)