引：真的是烦，连个hadoop集群环境都搭不好，发现一个人学还是很困难的，想想还是一个人看算法会简单些，所以来看看了，今天看堆排序！
堆排序
简单介绍
堆排序是原址运算，后来由于Java的原因我用了变址，但是算法的思想还是没有变得的.堆分为大顶堆，小顶堆，我们下面以大顶堆为例。
维护堆
我们需要一个函数在任何情况下子节点要比根节点小。
函数如下：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//取父节点
public int parent(int i){
return (int)Math.ceil(i/2)-1;
}
//取左子树
public int left(int i){
if(i == 0){
return i+1;
} else{
return 2*i+1;
}
}
//取右子树
public int right(int i){
if(i == 0){
return i+2;
} else{
return 2*i+2;
}
}
//维护大顶堆
public int[] max_heapify(int[] a,int i){
int l = left(i);
int r = right(i);
int largest = 0;
int temp = 0;
if(l>=a.length && r>=a.length){
return a;
}
if(l<a.length && a[l]>a[i]){
largest = l;
} else{
largest = i;
}
if(r<a.length && a[r]>a[largest]){
largest = r;
}
if(largest!=i) {
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest);
}
return a;
}
建堆
在对数组遍历建立二叉树的时候，我们容易得出Math.floor(n/2)到n都是叶节点，其余是根节点，所以我们在建堆得时候冲根节点不断往前维护就好。
代码如下：1
2
3
4
5
6
7
8//建大堆
public int[] bulid_max_heap(int[] a){
heap_size = a.length;
for(int i = (int)Math.floor(a.length/2)-1; i>=0; i--){
max_heapify(a, i);
}
return a;
}
堆排序算法
思想：先取出顶，再维护，再取顶，再维护，知道最后
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13//堆排序算法
public int[] heapsort(int[] a) {
int[] b = new int[a.length];//无奈之举，java没有size这个属性，或者用list也可以
bulid_max_heap(a);
for(int i = a.length-1; i>=1; i--){
b[i] = a[0];
a[0] = a[i];
a[i] = 0;//使最后一个元素不参与排序
max_heapify(a, 0);
}
b[0] = a[0];
return b;
}
算法时间复杂度：nlgn
重要应用——优先队列
优先队列应用于共享计算机的系统的作业调度，最大优先队列记录将要执行的各个作业以及它们之间的相对优先级，在任何时候都可以调用insert把一个新作业加入到队列中来。
讲一下最大优先序列的几个操作。
maximum获取最大值
代码如下：1
2
3
4 //获取最大值
public int maximum(int[] a){
return a[1];
}
去掉并返回数组中的最大键值得元素
代码如下:1
2
3
4
5
6
7
8
9
10//去掉并返回数组中具有最大键值得元素
public int extract_max(int[] a){
if(a.length<1){
System.out.println("heap underflow");
}
int max = a[0];
a[0] = a[a.length];
max_heapify(a, 0);
return max;
}
总结
加油呀加油！堆排序还是强大的，期待运用！