Thursday, October 27, 2016
Tuesday, October 25, 2016
Tuesday, October 18, 2016
Wednesday, October 5, 2016
Sunday, October 2, 2016
huffman encoding java
import java.util.Comparator;
import java.util.PriorityQueue;
public class HuffMan {
public static void main(String[] args) {
PriorityQueue<Node1> q = new PriorityQueue<Node1>(new Comparator<Node1>() {
public int compare(Node1 n1, Node1 n2) {
return n1.freq.compareTo(n2.freq);
}
});
q.add(new Node1('a',2));
q.add(new Node1('b',2));
q.add(new Node1('c',3));
q.add(new Node1('d',3));
q.add(new Node1('e',5));
q.add(new Node1('f',6));
q.add(new Node1('g',7));
while(q.size()>1) {
Node1 n1 = q.poll();
Node1 n2 = q.poll();
Node1 n3 = new Node1(' ',n1.freq+n2.freq);
n3.l = n1;
n3.r = n2;
q.add(n3);
}
dfs(q.peek(),"");
print(q.peek());
}
private static void print(Node1 root) {
if(root.l == null && root.r == null) System.out.println(root.val+" "+root.freq+" "+root.code);
else {
if(root.l != null) print(root.l);
if(root.r != null) print(root.r);
}
}
private static void dfs(Node1 root,String prefix) {
if(root.l == null && root.r == null) root.code = prefix;
else {
if(root.l != null) dfs(root.l,prefix+"0");
if(root.r != null) dfs(root.r,prefix+"1");
}
}
}
class Node1 {
Node1 l;
Node1 r;
char val;
Integer freq;
String code;
public Node1(char val,int freq) {
l = r = null;
this.val = val;
this.freq = freq;
}
}
Tuesday, September 27, 2016
Segment Tree Sum with Lazy Update
public class SegmentTreeSum {
private static int[] arr = {1,9,2,3,5,8,90,1,2,88};
private static Node[] stArr;
private static int[] lazy;
private static void update(int root,int low,int high,int diff) {
if(root>=stArr.length) return;
Node n = stArr[root];
//no intersection
if(low > n.r || high < n.l) {
return;
}
if(lazy[root] > 0) {
nonLazyUpdate(root,lazy[root]);
}
//n is contained between low & high
if(n.l >= low && n.r <= high) {
int totalDiff = (n.r - n.l + 1)*diff;
n.val += totalDiff;
updateParents(root,totalDiff);
int left = root*2+1;
int right = root*2+2;
if(left < stArr.length) lazy[left] = diff;
if(right < stArr.length) lazy[right] = diff;
return;
}
//low <= n.r && high >= n.l
update(root*2+1,low,high,diff);
update(root*2+2,low,high,diff);
}
private static void nonLazyUpdate(int root, int diff) {
if(root >= stArr.length) return;
Node n = stArr[root];
if(n==null) return;
n.val += diff*(n.r - n.l + 1);
lazy[root] = 0;
int leftChild = 2*root+1;
int rightChild = 2*root+2;
if(leftChild < stArr.length && lazy[leftChild] > 0) nonLazyUpdate(leftChild, lazy[leftChild]);
if(rightChild < stArr.length && lazy[rightChild] > 0) nonLazyUpdate(rightChild, lazy[rightChild]);
nonLazyUpdate(leftChild, diff);
nonLazyUpdate(rightChild, diff);
}
private static void updateParents(int root, int totalDiff) {
if(root==0) return;
int parent = (root - 1)/2;
Node n = stArr[parent];
n.val += totalDiff;
updateParents(parent,totalDiff);
}
private static int query(int root,int low,int high) {
//System.out.println("query");
if(root>=stArr.length) return 0;
Node n = stArr[root];
if(lazy[root] > 0) {nonLazyUpdate(root, lazy[root]);}
//no intersection
if(low > n.r || high < n.l) {
return 0;
}
//n is contained between low & high
if(n.l >= low && n.r <= high) {
return n.val;
}
//low <= n.r && high >= n.l
int l_sum = query(root*2+1,low,high);
int r_sum = query(root*2+2,low,high);
int sum = l_sum + r_sum;
return sum;
}
private static void construct(int root,int low,int high) {
if(high<low) return;
if(root>=stArr.length) return;
Node n = new Node(low,high);
stArr[root] = n;
if(low==high) { n.val = arr[low]; return;}
int mid = low + (high-low)/2;
construct(2*root+1,low,mid);
construct(2*root+2,mid+1,high);
Node left = stArr[2*root+1];
Node right = stArr[2*root+2];
int lval = left!=null?left.val:0;
int rval = right!=null?right.val:0;
n.val = lval + rval;
}
public static void main(String[] args) {
int stlen = (int) Math.ceil(Math.log(arr.length*1l)/Math.log(2l)) + 1;
stArr = new Node[(int)( Math.pow(2, stlen) - 1)];
lazy = new int[stArr.length];
construct(0,0, arr.length-1);
System.out.println(query(0,0,4));
update(0,0,9,1);
update(0,0,4,1);
update(0,1,1,1);
System.out.println(query(0,0,4));
}
}
class NodeS {
int l;
int r;
int val;
public NodeS(int l,int r) {
this.l = l;
this.r = r;
}
}
Monday, September 26, 2016
Segment Tree For Min Query Java
public class SegmentTreeMin {
private static int[] arr = {1,9,2,3,5,8,90,1,2,88};
private static Node[] stArr;
private static int query(int root,int low,int high) {
//System.out.println("query");
if(root>=stArr.length) return -1;
Node n = stArr[root];
//no intesection
if(low > n.r || high < n.l) {
return -1;
}
//n is contained between low & high
if(n.l >= low && n.r <= high) {
return n.val;
}
//low <= n.r && high >= n.l
int l_ind = query(root*2+1,low,high);
int r_ind = query(root*2+2,low,high);
int min = Integer.MAX_VALUE;
int min_index = -1;
if(l_ind > -1) {min = arr[l_ind];min_index = l_ind;}
if(r_ind > -1 && arr[r_ind] < min) {min = arr[r_ind];min_index = r_ind;}
return min_index;
}
private static void construct(int root,int low,int high) {
if(high<low) return;
if(root>=stArr.length) return;
Node n = new Node(low,high);
stArr[root] = n;
if(low==high) { n.val = low; return;}
int mid = low + (high-low)/2;
construct(2*root+1,low,mid);
construct(2*root+2,mid+1,high);
Node left = stArr[2*root+1];
Node right = stArr[2*root+2];
int lval = left!=null?arr[left.val]:Integer.MAX_VALUE;
int rval = right!=null?arr[right.val]:Integer.MAX_VALUE;
if(lval<rval) n.val = left.val; else n.val = right.val;
}
public static void main(String[] args) {
int stlen = (int) Math.ceil(Math.log(arr.length*1l)/Math.log(2l)) + 1;
stArr = new Node[(int)( Math.pow(2, stlen) - 1)];
construct(0,0, arr.length-1);
int min_index = query(0,5,7);
int minVal = min_index > -1?arr[min_index]:-1;
System.out.println(minVal);
/*for(int i=0;i<stArr.length;i++) {
Node n = stArr[i];
if(n!=null) {
System.out.println(i+" "+n.l+" "+n.r+" "+n.val);
}
}*/
}
}
class Node {
int l;
int r;
int val;
public Node(int l,int r) {
this.l = l;
this.r = r;
}
}
Subscribe to:
Posts (Atom)