堆排序啊，其实是一种数据结构，二叉树，二叉树分为是满二叉树和完全二叉树。一棵深度为 k，且有 2k - 1 个节点称之为满二叉树，完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树。

话收回来，堆呢，有最大堆，最小堆，最大堆是子节点没有比父节点小的，最小堆则相反。下面是堆排序，可以自己画一个草图自己画画，堆排序的过程。、


解决问题：

TopK问题是指从大量数据（源数据）中获取最大（或最小）的K个数据。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package  com.test1;
 
//堆排序
public  class  HeapSortFinal {
 
     public  static  void  main(String[] args) {
         int [] array = {  19 ,  38 ,  7 ,  36 ,  5 ,  5 ,  3 ,  2 ,  1 ,  0 ,  56  };
 
         System.out.println( "排序前:" );
         for  ( int  i =  0 ; i < array.length; i++) {
             System.out.print(array[i] +  "," );
         }
 
         System.out.println();
         System.out.println( "分割线---------------" );
 
         heapSort(array);
 
         System.out.println( "排序后:" );
         for  ( int  i =  0 ; i < array.length; i++) {
             System.out.print(array[i] +  "," );
         }
     }
 
     public  static  void  heapSort( int [] array) {
         if  (array ==  null  || array.length ==  1 )
             return ;
 
         buildMaxHeap(array);  // 第一次排序，构建最大堆，只保证了堆顶元素是数组里最大的
 
         for  ( int  i = array.length -  1 ; i >=  1 ; i--) {
             // 这个是什么意思呢？，经过上面的一些列操作，目前array[0]是当前数组里最大的元素，需要和末尾的元素交换
             // 然后，拿出最大的元素
             swap(array,  0 , i);
 
             // 交换完后，下次遍历的时候，就应该跳过最后一个元素，也就是最大的那个值，然后开始重新构建最大堆
             // 堆的大小就减去1，然后从0的位置开始最大堆
             maxHeap(array, i,  0 );
         }
     }
 
     // 构建堆
     public  static  void  buildMaxHeap( int [] array) {
         if  (array ==  null  || array.length ==  1 )
             return ;
 
         // 堆的公式就是 int root = 2*i, int left = 2*i+1, int right = 2*i+2;
         int  cursor = array.length /  2 ;
         for  ( int  i = cursor; i >=  0 ; i--) {  // 这样for循环下，就可以第一次排序完成
             maxHeap(array, array.length, i);
         }
     }
 
     // 最大堆
     public  static  void  maxHeap( int [] array,  int  heapSieze,  int  index) {
         int  left = index *  2  +  1 ;  // 左子节点
         int  right = index *  2  +  2 ;  // 右子节点
         int  maxValue = index;  // 暂时定在Index的位置就是最大值
 
         // 如果左子节点的值，比当前最大的值大，就把最大值的位置换成左子节点的位置
         if  (left < heapSieze && array[left] > array[maxValue]) {
             maxValue = left;
         }
 
         // 如果右子节点的值，比当前最大的值大，就把最大值的位置换成右子节点的位置
         if  (right < heapSieze && array[right] > array[maxValue]) {
             maxValue = right;
         }
 
         // 如果不相等，说明啊，这个子节点的值有比自己大的，位置发生了交换了位置
         if  (maxValue != index) {
             swap(array, index, maxValue);  // 就要交换位置元素
 
             // 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质：两个子节点都比父节点小。
             maxHeap(array, heapSieze, maxValue);
         }
     }
 
     // 数组元素交换
     public  static  void  swap( int [] array,  int  index1,  int  index2) {
         int  temp = array[index1];
         array[index1] = array[index2];
         array[index2] = temp;
     }
 
}