heapsort.java

实现heap排序的算法

import java.util.Random;

class Node
{
	private int iData;
	
	public Node(int key)
	{
		iData=key;
	}
	
	public int getKey()
	{
		return iData;
	}
	
	public void setKey(int id)
	{
		iData=id;
	}
}

class Heap
{
	private Node[] heapArray;
	private int maxSize;
	private int currentSize;
	
	public Heap(int mx)
	{
		maxSize=mx;
		heapArray=new Node[maxSize];
		currentSize=0;
	}
	
	public boolean isEmpty()
	{
		return currentSize==0;
	}
	
	public Node remove()
	{
		Node root=heapArray[0];
		heapArray[0]=heapArray[--currentSize];
		trickleDown(0);
		return root;
	}
	
	public void trickleDown(int index)
	{
		int largeChild;
		int leftChild,rightChild;
		Node top=heapArray[0];
		
		while(index<currentSize/2)
		{
			leftChild=2*index+1;
			rightChild=leftChild+1;
			
			if(rightChild<currentSize&&
				heapArray[leftChild].getKey()<heapArray[rightChild].getKey())
				largeChild=rightChild;
			else 
				largeChild=leftChild;
			
			if(top.getKey()>heapArray[largeChild].getKey())
				break;
			heapArray[index]=heapArray[largeChild];
			index=largeChild;
		}
		
		heapArray[index]=top;		
	}
	
	public void displayHeap()
	{
		System.out.println("heapArray: ");
		for(int m=0;m<currentSize;m++)
			if(heapArray[m]!=null)
				System.out.print(heapArray[m].getKey()+" ");
			else 
				System.out.print(".. ");
		System.out.println();
		
		int nBlanks=32;
		int itemsPerRow=1;
		int column=0;
		int j=0;
		String dots="................................";
		System.out.println(dots+dots);
		
		while(currentSize>0)
		{
			if(column==0)
				for(int k=0;k<nBlanks;k++)
					System.out.print(' ');
			System.out.print(heapArray[j].getKey());
			if(++j==currentSize)
				break;
			
			if(++column==itemsPerRow)
			{
				nBlanks/=2;
				itemsPerRow*=2;
				column=0;
				System.out.println();
			}				
			else 
				for(int i=0;i<nBlanks*2-2;i++)
					System.out.print(' ');
		}
		System.out.println("\n"+dots+dots);
	}
	
	public void displayArray()
	{
		for(int j=0;j<maxSize;j++)
			System.out.print(heapArray[j].getKey()+" ");
		System.out.println();
	}
	
	public void insertAt(int index,Node newNode)
	{
		heapArray[index]=newNode;
	}
	
	public void incrementSize()
	{
		currentSize++;
	}
}

public class HeapSort
{
	public static void main(String[] args)
	{
		Heap theHeap=new Heap(20);
		Random select=new Random();
		for(int i=0;i<20;i++)
		{	
			Node temp=new Node(select.nextInt(100));
			theHeap.insertAt(i,temp);
			theHeap.incrementSize();
		}
		for(int i=20/2-1;i>=0;i--)
			theHeap.trickleDown(i);
		theHeap.displayArray();
		
		for(int i=0;i<20;i++)
		{
			Node temp=theHeap.remove();
			theHeap.insertAt(19-i,temp);
		}
		
		theHeap.displayArray();
		
	}
}