堆结构的实现

把源码记录下来：

/**
* @author Administrator
*
*/
public class HeapSort {

/*
* 查找节点的父节点的位置，索引是从0开始的
*/
public static int parent(int i){
   return (i-1)>>1;
}
/**
* @param i
* @return
* 查找节点的左节点的位置，索引是从0开始的
*/
public static int left(int i){
   return (i<<1)+1;
}
/**
* @param i
* @return
* 查找节点的右节点的位置，索引是从0开始的
*/
public static int right(int i){
   return (i<<1)+2;
}

/**
* @param a
* @param start
* @param end
* 将a[start] 和 a[end] 的值进行交换
*/
public static void exchange(int[] a,int start,int end){
   int temp = a[start];
   a[start] = a[end];
   a[end] = temp;
}

/**
* @param a
* @param i
* @param heapSize
* 将a[i]下的所有子节点构造为一个最大堆
*/
public static void maxHeapify(int[] a,int i,int heapSize){
   int l,r,largest;
  
   l = left(i);
   r = right(i);
   if(l<heapSize && a[l]>a[i])
    largest = l;
   else
    largest = i;
  
   if(r<heapSize && a[r]>a[largest])
    largest = r;
   if(largest != i){
    exchange(a, i, largest);
    maxHeapify(a, largest, heapSize);
   }
}


/**
* @param a
* @param heapSize
* 从a数组的(n-1)/2处起，构造最大堆
*/
public static void buildMaxHeap(int[] a,int heapSize){
   int i;
  
   for(i=parent(heapSize);i>=0;i--){
    maxHeapify(a, i, heapSize);
   }
}

public static void heapSort(int[] a,int heapSize){
   int i;
   buildMaxHeap(a, heapSize);
   heapIncreaseKey(a, 9, 89);
   /*output......*/
   printf(a);
   /*
   * 下面的这个for 循环，从根节点处开始构造最大堆，在位置0处选出最大值，然后再将位置0片的调换到后面，使数组呈升序排列
   * */
   for(i = heapSize-1;i>0;i--){
    exchange(a, 0, i);
    heapSize--;
    maxHeapify(a, 0, heapSize);
   }
}
public static void printf(int[] a){
   int i=0;
   for(i=0;i<10;i++)
    System.out.println(a[i]);
}

/*优先级队列操作
* *HeapMaximum:返回堆的最大元素
*HeapExtractMax:删除堆的最大元，并调整重建堆
*HeapIncreaseKey:堆中某元素值增加，并调整重建堆
*MaxHeapInsert:将一个节点插入到堆中
* */
public static int heapMaximum(int[] a){
  
   return a[0];
}

public static int heapExtractMax(int[] a,int heapSize){
   int max;
   max = a[0];
   a[0] = a[heapSize-1];
   heapSize--;
   maxHeapify(a, 0, heapSize);
   return max;
}

public static void heapIncreaseKey(int[] a,int i,int key){
   a[i] = key;
   while(i>0 && a[parent(i)]<a[i]){
    exchange(a, parent(i), i);
    i = parent(i);
   }
}

public void maxHeapInsert(int[] a,int heapSize,int key){
   heapSize++;
   a[heapSize-1] = -100;
   heapIncreaseKey(a, heapSize-1, key);
}

public static void main(String[] args) {
  
   int i,heapSize;
   int a[] = {12,6,13,8,9,37,1,24,10,5};
  
   heapSize = 10;
   heapSort(a,heapSize);
   /*output.....*/
   printf(a);
}
}