Java数据结构与排序算法——堆和堆排序

//=================================================
// File Name       :Heap_demo
//------------------------------------------------------------------------------
// Author          :Common//类名：Node_Heap
//属性：
//方法：
class Node_Heap{
public int iData;public Node_Heap(int iData) {//构造函数
super();
this.iData = iData;
}public int getiData() {
return iData;
}public void setiData(int iData) {
this.iData = iData;
}
}//类名：Heap
//属性：
//方法：
class Heap{
private Node_Heap[] heapArray;
public int maxSize;
private int currentSize;public Heap(int maxSize) {//构造函数
super();
this.maxSize = maxSize;
this.currentSize = 0;
heapArray = new Node_Heap[maxSize];
}public boolean isEmpty(){
return currentSize ==0;
}public boolean insert(int key){
if(currentSize == maxSize){
return false;
}
Node_Heap newNode = new Node_Heap(key);
heapArray[currentSize] = newNode;//把插入的节点放在最后的位置
trickleUp(currentSize++);//插入节点并把currentSize加1
return true;
}//用于插入，把父类节点下移，然后把插入的节点放到合适的位置
public void trickleUp(int index){
int parent = (index-1)/2;
Node_Heap bottom = heapArray[index];//暂存新插入的节点，因为需要把父节点下移
while(index>0 && heapArray[parent].getiData()<bottom.getiData()){//如果小，就下移
heapArray[index] = heapArray[parent];//把父类节点下移
index = parent;//用于递归
parent = (parent-1)/2;
}
heapArray[index] = bottom;//把插入的节点放到合适的位置
}public Node_Heap remove(){//删除最大的节点
Node_Heap root = heapArray[0];
heapArray[0]=heapArray[--currentSize];
trickleDown(0);
return root;
}//用于删除，把子类节点上移
public void trickleDown(int index){
int largerChild;
Node_Heap top = heapArray[index];//
while(index<currentSize/2){//如果小，就下移
int leftChild = 2*index+1;
int rightChild = leftChild+1;
if(rightChild<currentSize && heapArray[leftChild].getiData() < heapArray[rightChild].getiData())
largerChild = rightChild;
else
largerChild = leftChild;
if(top.getiData()>=heapArray[largerChild].getiData())
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}public void displayHeap(){
System.out.print("heapArray:");
for(int i=0;i<heapArray.length;i++){
if(heapArray[i] != null)
System.out.print(heapArray[i].getiData()+" ");
else
System.out.print(" -- ");
}
System.out.println();int nBlanks = 32;//定义空格
int itemsPerRow = 1;
int column = 0;
int j=0;//标记当前的数组下标，从0开始
System.out.println("......................................................");
while(currentSize > 0){
if(column == 0){
for(int i=0;i<nBlanks;i++){
System.out.print(" ");
}
}
System.out.print(heapArray[j].getiData());
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"+"......................................................");
}}//主类
//Function        : Heap_demo
public class Heap_demo {public static void main(String[] args) {
// TODO 自动生成的方法存根
int anArrays[]={1,2,3,4,5,6,7,8,9,10};
Heap theHeap = new Heap(31);
//theHeap.insert(1);
//theHeap.insert(2);
//theHeap.insert(3);
//theHeap.insert(4);
//theHeap.insert(5);
//theHeap.insert(6);
for(int i=0;i<10;i++){
theHeap.insert(anArrays[i]);
}
theHeap.displayHeap();
//theHeap.remove();
//theHeap.displayHeap();
for(int i=0;i<10;i++){
anArrays[i]=theHeap.remove().iData;
}
for(int i=0;i<10;i++){
System.out.print(anArrays[i]+" ");
}
}}