heap.java

实现数据库的storage manager 功能

/*
 * Copyright (c) 2000-2004, Rickard C鰏ter, Martin Svensson
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 * Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer. 
 * Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution. 
 * Neither the name of SICS nor the names of its contributors 
 * may be used to endorse or promote products derived from this software 
 * without specific prior written permission. 
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 *
 *
 */

package com.mellowtech.disc.sort;

/**
 * A Simple Heap (priority queue).
 *
 * @author Martin Svensson
 * @version 1.0
 */
public class Heap{
  private Comparable heap[];
  private float inc;
  private int size;

  private Heap(){
    ;
  }

  /**
   * Create a new heap with an initial capacity.
   * @param initSize this heaps initial capacity
   */
  public Heap(int initSize){
    size = 0;
    heap = new Comparable[initSize];
    inc = 2.0f;
  }

  /**
   * Create a new heap with an inital capacity and specificed growth factor.
   *
   * @param initSize this heap's initial capacity
   * @param incrementFactor how much the heap shold grow when reallocation is needed, defaults to 200%
   */
  public Heap(int initSize, float incrementFactor){
    heap = new Comparable[initSize];
    inc = incrementFactor;
    size = 0;
  }

  /**
   * Insert a new object into this heap
   * @param c the object to insert
   */
  public void insert(Comparable c){
    if(size == heap.length) resize();
    
    //bubble up:
    int child = ++size;
    
    while(child > 1 && c.compareTo(heap[(child / 2)-1]) < 0){
      heap[child - 1] = heap[(child / 2) - 1];
      child /= 2;
    }
    heap[child-1] = c;
  }

  /**
   * Set this heap's size to 0.
   *
   */
  public void clear(){
    size = 0;
  }

  /**
   * Return the number of objects in this heap
   * @return number of objects
   */
  public int size(){
    return size;
  }

  /**
   * Get the first (smallest) object in this heap.
   * @return the smallest object
   */
  public Comparable get(){
    return heap[0];
  }

  public Comparable get(int i){
    return heap[i];
  }

  /**
   * Delete the first (smallest) object in this heap.
   *
   * @return the deleted object
   */
  public Comparable delete(){
    if(size == 0)
      return null;
    Comparable T = heap[0];
    size--;
    heap[0] = heap[size];
    bubbleDown(heap, 1, size);
    return T;
  }

  /**
   * Turn an array of objects into a heap.
   *
   * @param objs the objects to convert.
   * @return a new heap
   */
  public static Heap heapify(Comparable[] objs){
    int N = objs.length;
    for(int k = N/2; k > 0; k--){
      bubbleDown(objs, k, N);
    }
    System.out.println(objs[0]);
    Heap h = new Heap();
    h.size = objs.length;
    h.heap = objs;
    return h;
  }

  /**
   * Sort an array of objects.
   * @param objs the objects to sort
   */
  public static void heapSort(Comparable[] objs){
    int N = objs.length;
    for(int k = N/2; k > 0; k--){
      bubbleDownReverse(objs, k, N);
    }
    //System.out.println("This is object 0: "+objs[0]);
    do{
      Comparable T = objs[0];
      objs[0] = objs[N - 1];
      objs[N - 1] = T;
      N = N - 1;
      bubbleDownReverse(objs, 1, N);
    } 
    while (N > 1);
  }
  
  public String toString(){
    StringBuffer sb = new StringBuffer();
    for(int i = 0; i < size; i++)
      sb.append(heap[i]+"\t");
    return sb.toString();
  }

  private void resize(){
    Comparable o[] = new Comparable[Math.round(heap.length * inc)];
    System.arraycopy(heap, 0, o, 0, heap.length);
    heap = o;
  }

  private static void bubbleDown(Comparable[] objs, int node, int max){
    //node = node, objs = objects to bubble, max = max size;
    Comparable T = objs[node - 1];
    int half = max/2;
    while(node <= half){
      int j = node + node;

      if((j < max) && (objs[j - 1].compareTo(objs[j]) > 0)){
	j++;
      }

      if(T.compareTo(objs[j-1]) > 0){
	objs[node - 1] = objs[j - 1];
	node = j;
      }
      else
	break;
    }
    objs[node - 1] = T;
  }

  private static void bubbleDownReverse(Comparable[] objs, int k, int N){
    //int T = a[k - 1];
    Comparable T = objs[k - 1];
    while(k <= N/2){
      int j = k + k;
      if((j < N) && (objs[j - 1].compareTo(objs[j]) < 0)){
	j++;
      }
      if(T.compareTo(objs[j-1]) >= 0){
	break;
      }
      else{
	objs[k - 1] = objs[j - 1];
	k = j;
      }
    }
    objs[k - 1] = T;
  }
}