现在的位置: 首页 > 综合 > 正文

堆结构的实现

2013年07月10日 ⁄ 综合 ⁄ 共 4700字 ⁄ 字号 评论关闭

包括最大值堆和最小值堆:

接口:

package org.rut.util.structure.heap;

/**
 * @author treeroot
 * @since 2006-1-31
 * @version 1.0
 */
public interface Heap {
    /**
     * return the top element of the heap
     * @return top element
     */
    Object get();
    /**
     * remove the top element of the heap and return it
     * the heap must be fixed.
     * @return top element
     */
    Object remove();
   
    /**
     * reset the top element
     * @param obj the new top element
     */
    void set(Object obj);
    /**
     * add a element to the heap.
     * if no comparator is set, the obj must be implments comparable interface
     * @param obj the element to be added
     */
    void add(Object obj);
    /**
     * if the heap is empty return true;
     * @return true if heap is empty,else false
     */
    boolean isEmpty();
    /**
     * clear the heap
     */
    void clear();
}

package org.rut.util.structure.heap;

import java.util.Comparator;

/**
 * @author treeroot
 * @since 2006-1-31
 * @version 1.0
 */
public abstract class AbstractHeap implements Heap {

    private int size;

    private Object[] queue = new Object[128];

    private Comparator comp;

    public AbstractHeap() {
        this(new Comparable[0]);
    }

    public AbstractHeap(Comparable[] elements) {
        init(elements);
    }

    public AbstractHeap(Comparator comp, Object[] elements) {
        this.comp = comp;
        if (this.comp == null)
            throw new IllegalArgumentException("compartor can't be null");
        init(elements);
    }

    private void init(Object[] elements) {
        for(int i=0;i<elements.length;i++) add(elements[i]);
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#get()
     */
    public Object get() {
        return queue[1];
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#remove()
     */
    public Object remove() {
        Object ret = queue[1];
        queue[1] = queue[size];
        queue[size--] = null; // Drop extra reference to prevent memory leak
        fixDown(1);
        return ret;
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#set(java.lang.Object)
     */
    public void set(Object obj) {
        check(obj);
        queue[1] = obj;
        fixDown(1);
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#add(java.lang.Object)
     */
    public void add(Object obj) {
        check(obj);
        if (++size == queue.length) {
            Object[] newQueue = new Object[2 * queue.length];
            System.arraycopy(queue, 0, newQueue, 0, size);
            queue = newQueue;
        }
        queue[size] = obj;
        fixUp(size);
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#isEmpty()
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.structure.heap.Heap#clear()
     */
    public void clear() {
        for (int i = 1; i <= size; i++)
            queue[i] = null;
        size = 0;
    }
    //check the type
    private void check(Object element) {
        if (this.comp == null) {
            if (!(element instanceof Comparable))
                throw new IllegalArgumentException(
                        "element must be Comparble when no Comparator is set");
        }
    }
    //compare may be override by subclass
    protected int compare(int i,int j){
        if(comp!=null) return comp.compare(queue[i],queue[j]);
        return ((Comparable)queue[i]).compareTo(queue[j]);
    }
    //fixup
    private void fixUp(int k) {
        while (k > 1) {
            int j = k >> 1;
            if (compare(j,k)<=0)
                break;
            Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }
    //fixdown
    private void fixDown(int k) {
        int j;
        while ((j = k << 1) <= size) {
            if (j < size && compare(j,j+1)>0 )
                j++; // j indexes smallest kid
            if (compare(k,j)<=0) //不用交换
                break;
            Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

}

最大值堆:

package org.rut.util.structure.heap;

import java.util.Comparator;

/**
 * @author treeroot
 * @since 2006-1-31
 * @version 1.0
 */
public class MaxHeap extends AbstractHeap implements Heap{
    public MaxHeap() {
        super();
    }

    public MaxHeap(Comparable[] elements) {
        super(elements);
    }

    public MaxHeap(Comparator comp, Object[] elements) {
        super(comp,elements);
    }

  
    /* (non-Javadoc)
     * @see org.rut.util.structure.heap.AbstractHeap#compare(int, int)
     */
    protected int compare(int i, int j) {
        return super.compare(j, i);
        //use compare(j,i) instead of -compare(i,j)
    }
}

最小值堆(默认就是):

package org.rut.util.structure.heap;

import java.util.Comparator;

/**
 * @author treeroot
 * @since 2006-1-31
 * @version 1.0
 */
public class MinHeap  extends AbstractHeap implements Heap{
   
    public MinHeap() {
        super();
    }

    public MinHeap(Comparable[] elements) {
        super(elements);
    }

    public MinHeap(Comparator comp, Object[] elements) {
        super(comp,elements);
    }
    /* (non-Javadoc)
     * @see org.rut.util.structure.heap.AbstractHeap#compare(int, int)
     */
    protected int compare(int i, int j) {
        return super.compare(i, j);
    }
}

 

抱歉!评论已关闭.