学步园

http://blog.sina.com.cn/s/blog_534408920100acqv.html   堆的介绍：

1. 堆的介绍：堆是一种数组，但是以树的结构形式来看待它，如下标 i 节点的求解Parent和Children节点如下：

   PARENT(i) return ⌊i/2⌋ 
   LEFT(i) return 2i 
    
    
   RIGHT(i) return 2i + 1 

    堆分为MAX-堆和MIN-堆，
   MAX堆满足的条件为： A[PARENT(i)]≥
   A[i] ,
   MIN堆满足的条件为： A[PARENT(i)]≤
   A[i] .
   

2. MAX和MIN堆的维持：
   这里只对MAX堆，MIN对类似：数组A的LEFT(i) 和 RIGHT(i) 都是MAX堆，但可能A[ i ]可能小于它的Children节点，所以需要调整，调整伪代码如下：

MAX-HEAPIFY(A, i)
 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4    then largest ← l
 5    else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7    then largest ← r
 8 if largest ≠ i
 9    then exchange A[i] ↔ A[largest]
10         MAX-HEAPIFY(A, largest)

MAX堆建立：
 

BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← ⌊length[A]/2⌋ downto 1
3       do MAX-HEAPIFY(A, i)  

 如下面建立MAX过程：

4 堆排序(HeapSort)
首先是把一个给定的数组变成MAX堆，然后把根节点和堆的最后一个交换，堆的大小减1，再调整堆，
这样下去，直到堆的大小为1：
伪代码如下：

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i ← length[A] downto 2
3    do exchange A[1] ↔ A[i]
4       heap-size[A] ← heap-size[A] - 1
5       MAX-HEAPIFY(A, 1) 

 堆排序时一种不稳定的排序，辅助空间为O(1),最坏的时间为O(Nlog2N),堆排序的堆序的平均性能较接近最坏性能

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(DataWraper[] data){
        System.out.println("开始排序");
        int arrayLength=data.length;
        //循环建堆
        for(int i=0;i<arrayLength-1;i++){
            //建堆
            buildMaxHeap(data,arrayLength-1-i);
            //交换堆顶和最后一个元素
            swap(data,0,arrayLength-1-i);
            System.out.println(Arrays.toString(data));
        }
    }

    private static void swap(DataWraper[] data, int i, int j) {
        // TODO Auto-generated method stub
        DataWraper tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
    //对data数组从0到lastIndex建大顶堆
    private static void buildMaxHeap(DataWraper[] data, int lastIndex) {
        // TODO Auto-generated method stub
        //从lastIndex处节点（最后一个节点）的父节点开始
        for(int i=(lastIndex-1)/2;i>=0;i--){
            //k保存正在判断的节点
            int k=i;
            //如果当前k节点的子节点存在
            while(k*2+1<=lastIndex){
                //k节点的左子节点的索引
                int biggerIndex=2*k+1;
                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
                if(biggerIndex<lastIndex){
                    //若果右子节点的值较大
                    if(data[biggerIndex].compareTo(data[biggerIndex+1])<0){
                        //biggerIndex总是记录较大子节点的索引
                        biggerIndex++;
                    }
                }
                //如果k节点的值小于其较大的子节点的值
                if(data[k].compareTo(data[biggerIndex])<0){
                    //交换他们
                    swap(data,k,biggerIndex);
                    //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    k=biggerIndex;
                }else{
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DataWraper [] data={
                new DataWraper(21, ""),
                new DataWraper(30, ""),
                new DataWraper(49, ""),
                new DataWraper(30, "*"),
                new DataWraper(16, ""),
                new DataWraper(9, ""),
               
        };
        System.out.println("排序之前：\n"+Arrays.toString(data));
        heapSort(data);
        System.out.println("排序之后：\n"+Arrays.toString(data));
    }

}

结果

排序之前：
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 21, 30*, 16, 49]
[16, 30*, 21, 9, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
排序之后：
[9, 16, 21, 30*, 30, 49]