heap.java

国外的数据结构与算法分析用书

public class Heap
{
	/**	Create a heap for the sequence. */
	public void createHeap(int[ ] inVec)
	{
		for (int size = 1; size < inVec.length; size++)
			insertLeaf(inVec, size);
	}

	/**	Add a leaf at position pos. */
	public void insertLeaf(int[ ] inVec, int pos)
	{
		int newItem = inVec[pos];  // the leaf item to be added
		int childPos = pos;
		int parentPos = (childPos - 1) / 2;
		while ((childPos != 0) && (newItem > inVec[parentPos]))
		{
			inVec[childPos] = inVec[parentPos]; // move parent value to child position
			childPos = parentPos;
			parentPos = (childPos - 1) / 2;
		}
		inVec[childPos] = newItem; // copy leaf item to its proper place
	}

	/**	Perform a heap sort on inVec. */
	public void heapSort(int[ ] inVec)
	{
		createHeap(inVec);
		for (int heapEnd = inVec.length - 1; heapEnd > 0; heapEnd--)
		{
			/*	Swap item 0 and heapEnd, so that the largest item of the heap is
				moved to heapEnd, and then shift the new root down as far as necessary. */
			int temp = inVec[0];
			inVec[0] = inVec[heapEnd];
			inVec[heapEnd] = temp;
			reconstructHeap(inVec, heapEnd - 1);
		}
	}

	/**	Reconstruct heap in locations 0 ... heapEnd by shifting the root item 
		downwards as far as necessary. */
	public void reconstructHeap(int[ ] inVec, int heapEnd)
	{
		int curKey = inVec[0]; // the value whose position is being corrected
		int parent = 0;  // index of the current position for curKey
		int largest; // index of largest child of parent
		if ((heapEnd >= 2) && (inVec[2] > inVec[1]))
			largest = 2;
		else
			largest = 1;
		while ((largest <= heapEnd) && (inVec[largest] > curKey))
		{
			inVec[parent] = inVec[largest]; // move largest child to the current parent position
			parent = largest; // update position for the current item
		
			int left = parent * 2 + 1; // index of the left child of the current parent
			if ((left + 1 <= heapEnd) && (inVec[left + 1] > inVec[left]))
				largest = left + 1;
			else
				largest = left;
		}
		inVec[parent] = curKey; // copy item into its proper place
	}
}