priorityqueue.java

排队论模拟,最近刚刚找到的

/*
##############################################################################################################
	Wal-Mart Checkout Simulation
	By: Dustin Grimmeissen and Richard Anderson

	-> Priority Queue Class

	This is the class used to store each arrival or departure event in the order that they are to execute.
##############################################################################################################
*/

public class PriorityQueue
{
	int size; 					
	Event heap[] = new Event[1000];

	// Constructor
	public void PriorityQueue()
	{
		size = 0;
	}

	//----------------------------------------------------------------------------
	// enqueue - Receives a customer as input along with the priority value and
	//           whether or not it is an arrival event or a departure event. 
	//----------------------------------------------------------------------------
	public void enqueue(Customer aCust, long priority, int type)
	{
		heap[size] = new Event(aCust, priority, type);
		++size;
		filterUp(size-1);
	}

	//----------------------------------------------------------------------------
	// dequeue - Pops the top item off of the heap and filters down all other events
	//           left in the priority queue.
	//----------------------------------------------------------------------------
	public Event dequeue()
	{
		if (size != 0)
		{
			Event theEvent = heap[0];

			--size;

			if (size != 0)
			{
				swap(0, size);
				filterDown(0);
			}

			return theEvent;
		}
		else
		{
			Customer nullCustomer = new Customer(-1);
			Event nullEvent = new Event(nullCustomer, 0, 0);
			return nullEvent;
		}
	}

	public int getSize()
	{
		return size;
	}

	//----------------------------------------------------------------------------
	// filterUp - Filters a new item up the heap to its correct position.
	//----------------------------------------------------------------------------
	private void filterUp(int idx)
	{
		if (idx > 0 && idx < size)
		{
			int parentIdx = (int)((idx-1)/2);
			if (heap[idx].getPriority() < heap[parentIdx].getPriority())
			{
				swap(idx, parentIdx);
			}
			filterUp(parentIdx);
		}
	}

	//----------------------------------------------------------------------------
	// filterDown - Filters an item down the heap to its correct position.
	//----------------------------------------------------------------------------
	private void filterDown(int idx)
	{
		int leftChildIdx = idx*2 + 1;
		int rightChildIdx = idx*2 + 2;

		if (leftChildIdx < size)
		{
			if (rightChildIdx < size)
			{
				if (heap[leftChildIdx].getPriority() < heap[rightChildIdx].getPriority())
				{
					if (heap[leftChildIdx].getPriority() < heap[idx].getPriority())
					{
						swap(leftChildIdx, idx);
						filterDown(leftChildIdx);
					}
				}
				else
				{
					if (heap[rightChildIdx].getPriority() < heap[idx].getPriority())
					{
						swap(rightChildIdx, idx);
						filterDown(rightChildIdx);
					}
				}
			}
			else
			{
				if (heap[idx].getPriority() > heap[leftChildIdx].getPriority())
				{
					swap(idx, leftChildIdx);
					filterDown(leftChildIdx);
				}
			}
		}
	}

	//----------------------------------------------------------------------------
	// swap - Swaps two nodes of the heap.
	//----------------------------------------------------------------------------
	private void swap(int a, int b)
	{
		Event tmp;
		tmp = heap[a];
		heap[a] = heap[b];
		heap[b] = tmp;
	}
};