heap.java

java 实现常用数据结构（链表

/*
 * Heap.
 * @Author: zhengbotai.
 * @Date: 2007.5
*/

// Heap data structure.
package dreamer.util;

class HeapStruct
{
	int [] heap;
	int len;
	int MAX_SIZE;
}

public class Heap 
{
	// create a heap and initialize the const variable.
	public void createHeap(HeapStruct HS)
	{
		HS.MAX_SIZE = 100;
		HS.len = 0;
	}
    
    // insert the object to a feat position.
	public void insert(HeapStruct HS,int obj)
	{
		HS.heap[HS.len] = obj;
		HS.len++;
		int i = HS.len - 1;
		while(i!=0)
		{
			int j = (i-1)/2;
			if(obj>=HS.heap[j])
				break;
			HS.heap[i] = HS.heap[j];
			i = j;
		}
		HS.heap[i] = obj;
	}
	
	// delete the top of the heap.
	public int delete(HeapStruct HS)
	{
		int temp;
		if(HS.len == 0)
			return -1;
		temp = HS.heap[0];
		HS.len --;
		if(HS.len == 0)
			return temp;
		int t =HS.heap[HS.len];
		int i = 0;
		int j = i*2+1;
		while(j<=HS.len-1)
		{
			if(j<HS.len-1 && HS.heap[j]>HS.heap[j+1])
				j++;
			if(t<=HS.heap[j])
				break;
			HS.heap[i] = HS.heap[j];
			i = j;
			j = i*2+1;
		}
	    HS.heap[i] = t;
	    return temp;		
	}
	
	// clear all heap nodes.
	public void clear(HeapStruct HS)
	{
		if(HS.heap!=null)
		{
			HS.heap = null;
			HS.len = 0;
			HS.MAX_SIZE = 0;
		}
	}
	
}