显示标签为“Data Structure”的博文。显示所有博文
显示标签为“Data Structure”的博文。显示所有博文

2014年11月17日星期一

[Data Structure] Segment Tree

Segment Tree is useful for range sum and update. Given an array A, we have two types of query, one is give the sum of elements in the range [l ,..., r] and the other is update the A[i] with a incremental or decrease. Using Segment Tree, both of the two operation can be done in O(logn) time.

Here is a more detail post about segment tree:http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/


import java.util.*;

public class SegmentTree {
 public static class TreeNode {
  int val, l ,r;
  TreeNode left, right;
  public TreeNode(int val, int l, int r) {
   this.val = val;
   this.l = l;
   this.r = r;
  }
 }
 
 public static TreeNode buildTree(int[] A, int l, int r) {
  if(l == r) {
   TreeNode node = new TreeNode(A[l], l, r);
   return node;
  }
  else {
   int mid = l + (r - l) / 2;
   TreeNode left = buildTree(A, l, mid);
   TreeNode right = buildTree(A, mid+1, r);
   TreeNode node = new TreeNode(left.val + right.val, l, r);
   node.left = left;
   node.right = right;
   return node;
  }
 }
 
 public static int getSum(TreeNode node, int l, int r) {
  if(node.l >= l && node.r <= r) {
   return node.val;
  }
  else if(node.r < l || node.l > r) {
   return 0;
  }
  else {
   return getSum(node.left, l, r) + getSum(node.right, l, r);
  }
 }
 
 public static void update(TreeNode node, int val, int ind) {
  if(node == null)
   return;
  if(node.l > ind || node.r < ind) {
   return;
  }
  else {
   node.val += val;
   update(node.left, val, ind);
   update(node.right, val, ind);
  }
 }
 
 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   int n = scan.nextInt();
   int[] A = new int[n];
   for(int i = 0; i < n; i++)
    A[i] = scan.nextInt();
   TreeNode root = buildTree(A, 0, n-1);
   update(root, 2, 0);
   update(root, 100, 3);
   update(root, -9, 9);
   int l, r;
   while(scan.hasNext()) {
    l = scan.nextInt();
    r = scan.nextInt();
    System.out.println(getSum(root, l, r));
   }
  }
 }
}

2014年11月15日星期六

[Data Structure] Find the kth largest or kth smallest elements in a given array

Given an array, which is not ordered. You are asked to find all kth largest or kth smallest elements in it.

This question is quite popular. A very naive method is to sort the array first, then we find all kth largest or kth smallest elements. The time complexity is typically O(nlogn).
However, we could use a data structure called heap to improve the time complexity.

We first handle the kth largest case. In this case, we could use a small-end heap with capacity k. Then we sweep the array, for each element, if the heap is not full, we put it in, other wise we compare it with the top element of the heap, if it is larger than the top, we throw the current top away and put the element into heap. At the end, the heap will filled with kth largest elements, with the smallest one exist on the top.

Why this work? We consider the situation when the heap is full. The top would be the smallest one among all k elements. When a new element is less than or equal to the top, we know that it could not be selected, since there already exist k elements large or equal to it. What if a new element is larger than top? we know top could be eliminate, since we have a new candidate, by removing the top, we get a group of better k large elements. So we remove the top and put the new element in. The process continue until we have examine all elements in the array. The time complexity is O(nlogk), so if k << n, it will much faster than O(nlogn).

Similarly, for the kth smallest case, we use big-end heap with capacity k. 

The code is below, we use PriorityQueue in Java as the heap and pass a comparator to it. We assume the input would be valid.


 public static void FindKthSmall(int[] A, int k) {
  int n = A.length;
  Comparator<Integer> myComparator = new Comparator<Integer>() {
   public int compare(Integer a, Integer b) {
    return b - a;
   }
  };
  PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, myComparator);
  for(int i = 0; i < n; i++) {
   if(pq.size() == k) {
    if(A[i] < pq.peek()) {
     pq.remove();
     pq.add(A[i]);
    }
   }
   else {
    pq.add(A[i]);
   }
  }
  while(pq.size() != 0) {
   System.out.print(pq.peek() + " ");
   pq.remove();
  }
  System.out.println("");
 }


 public static void FindKthLarge(int[] A, int k) {
  int n = A.length;
  PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k);
  for(int i = 0; i < n; i++) {
   if(pq.size() == k) {
    if(A[i] > pq.peek()) {
     pq.remove();
     pq.add(A[i]);
    }
   }
   else {
    pq.add(A[i]);
   }
  }
  while(pq.size() != 0) {
   System.out.print(pq.peek() + " ");
   pq.remove();
  }
  System.out.println("");
 }