基本算法堆排序及其Java实现

(二叉)堆(heap)数据结构是一种数组对象，可以视作一颗完全二叉树，从该二叉树的根开始层次遍历这颗二叉树就可以得到其对应的数组。树的根节点为A[0]，对于树中某个节点的坐标i，其左右孩子节点和父亲节点的坐标可以很方便的求得：

LEFT(i)=2*i+1; RIGHT(i)=2*i+2; PARENT(i)=i/2 .

有两种二叉堆：最大堆和最小堆。最大堆中，每个节点存储的数值都大于等于其左右两个孩子节点存储的数值,亦即A[i]>=A[LEFT[i]]&&A[i]>=A[RIGHT[i]]。最小堆则正好相反。本文以最大堆为例。

知道了最大堆的定义之后，就要在给定的任意数组上构建最大堆，然后利用这个最大堆进行升序排序：

(1) 构建最大堆：

首先我们定义一个方法Heapify(heap，i)，如果以i的左右孩子节点为根的子树已经是最大堆，则该方法使得以i为根的子树也成为最大堆。其伪代码如下(摘自《算法导论》)：

 1 MAX-HEAPIFY(A,i)
 2  l=LEFT(i)
 3  r=RIGHT(i)
 4  target=i;
 5  if(l<=A.heap_size&&A[l]>A[i])
 6    target=l;
 7  if(if(r<=A.heap_size&&A[r]>A[i]))
 8    target=r;
 9  if(target!=i)
10    exchange(A[i],A[target])
11    MAX-HEAPIFY(A,target)//递归

我们比较当前节点i的数值和其左右子节点的数值，如果i的某个子节点的数值大于i的数值，则违反了最大堆的定义，所以我们需要交换这两个节点的位置。假设A[LEFT[i]]>A[RIGHT[i]]>A[i],则交换i节点与LEFT[i]节点。但是，被交换到左孩子节点的i节点可能会违反以左孩子结点为根的最大堆的定义，所以我们需要对这个最大堆递归调用MAX-HEAPIFY方法。

有了上面这个方法之后，我们就可以自底向上的调用MAX-HEAPIFY方法构建最大堆。因为A[A.length/2+1]及其之后的节点都是叶子节点，都可以看做只有一个节点的最大堆，所以我们可以从A[A.length/2]节点开始直到A[0]节点依次调用MAX-HEAPIFY方法，亦即从树的层次遍历的最后一个有孩子的节点开始，按照层次遍历的逆序调用MAX-HEAPIFY方法：

1 BUILD-MAX-HEAP(A)
2  for i=A.length/2 downto 1
3     MAX-HEAPIFY(A,i)

(2) 堆排序

构造完最大堆之后，我们就可以利用其进行排序。因为最大堆只能保证A[0]存储的是当前堆中最大的元素，我们可以把A[0]与堆的最后一个元素互换，这样A[0]就排在了最后一个位置，也是正确的位置。这时最后一个位置已经不属于最大堆，所以A.heap_size要减一。互换到A[0]的元素可能会破坏最大堆的性质，我们可以调用MAX-HEAPIFY方法使之重新成为最大堆，然后将A[0]交换至当前堆的最后一个位置。依次递归。

1 HEAPSORT(A)
2   for i=A.length downto 2
3     exchange(A[i],A[0])
4     --A.heap_size //堆的大小减少
5     MAX-HEAPIFY(A,0)

(3) 堆的JAVA实现

 1 package Algorithm;
 2 
 3 import java.util.*;
 4 /**
 5  * 堆(Heap)
 6  * @author Kemaswill
 7  * 2012-10-5 Friday
 8  */
 9 
10 public class Heap {
11     
12     public static int[] data;
13     public static int length;
14     public static int heap_size;
15     
16     public Heap(){
17         this.length=20;
18         this.heap_size=length;
19         this.data=new int[length];
20         Random random=new Random(System.currentTimeMillis());
21         for(int i=0;i<length;i++){
22             data[i]=Math.abs(random.nextInt()%50);
23         }//for
24     }
25     
26     public Heap(int n){
27         this.length=n;
28         this.heap_size=length;
29         this.data=new int[length];
30         Random random=new Random(System.currentTimeMillis());
31         for(int i=0;i<length;i++){
32             data[i]=Math.abs(random.nextInt()%50);
33         }//for
34     }
35     
36     public static void max_heapify(Heap heap,int i){
37         if(i<heap.heap_size){
38             int l=2*i+1;
39             int r=2*i+2;
40             int target=i;
41             if(l<heap.heap_size&&heap.data[l]>heap.data[i]){
42                 target=l;
43             }
44             if(r<heap.heap_size&&heap.data[r]>heap.data[target]){
45                 target=r;
46             }
47             if(target!=i){
48                 exchange(heap,i,target);
49                 max_heapify(heap,target);
50             }//if
51         }//if        
52     }//heapify
53     
54     public static void exchange(Heap heap,int x,int y){
55         int tmp=heap.data[x];
56         heap.data[x]=heap.data[y];
57         heap.data[y]=tmp;
58     }
59     
60     public static void build_heap(Heap heap){
61         //对于所有非叶结点，依次调用max_heapify
62         for(int i=heap.heap_size/2;i>=0;i--){
63             max_heapify(heap,i);
64         }
65     }
66     
67     public static void heapsort(Heap heap){
68         
69         for(int i=heap.length-1;i>0;i--){
70             exchange(heap,0,i);
71             heap.heap_size--;
72             max_heapify(heap,0);
73         }
74     }//heapsotr
75     
76     public static void show_heap(Heap heap){
77         for(int i=0;i<=(int)Math.log(heap.length)/Math.log(2)+2;i++){
78             for(int j=(int)Math.pow(2, i)-1;j<Math.pow(2, i+1)-1;j++){
79                 if(j<heap.length){
80                     System.out.print(heap.data[j]+" ");
81                 }
82                 else break;
83                 }
84             System.out.println();
85             }        
86     }
87     
88     public static void main(String[] args){
89         Heap heap=new Heap();
90         show_heap(heap);
91         build_heap(heap);
92         show_heap(heap);
93         heapsort(heap);
94         show_heap(heap);
95         
96     }//main
97 
98 }

参考文献：

[1] 《算法导论》第6章 p73

[2] 一个用Java实现的简单的最大堆