排序算法(二)--堆排序（JAVA）
堆的一个很重要的应用就是堆排序，和快速排序一样，堆排序的时间复杂度也是O(NlgN) 堆排序的实现思路一：
1.创建小根堆 2.每次删除顶部元素并将顶部元素输出（删除的函数中有调整的过程，每次调整） 时间复杂度：O(N·logN)
Input: 14 99 5 36 2 19 1 46 12 7 22 25 28 17 92
Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99
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
87import java.util.Scanner;
public class heap {
static int n, num = 0;
static int[] h = new int[15];
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
n = input.nextInt();
for (int i = 1; i <= n; i++) {
h[i] = input.nextInt();
}
num = n;
create();
for (int i = 1; i <= n; i++) {
System.out.print(deletemax() + " ");
}
}
private static void create() {
/**
* 从最后一个非叶结点到第1个结点向上调整
* */
for (int i = num / 2; i >= 1; i--) {
siftdown(i);
}
}
private static int deletemax() {
int temp = h[1];
h[1] = h[num];
num--;
siftdown(1);
return temp;
}
private static void siftup(int i) {
int flag = 0;
/**
* 堆顶
* */
if (i == 1) {
return;
}
while (i != 1 && flag == 0) {
/**
* 当前节点是否小于父结点
* */
if (h[i] < h[i/2]) {
int temp = h[i];
h[i] = h[i/2];
h[i/2] = temp;
} else {
flag = 1;
}
/**
* 向上调整
* */
i = i/2;
}
}
private static void siftdown(int i) {
int t, flag = 0;
while (i * 2 <= num && flag == 0) {
if (h[i] > h[i*2]) {
t = i * 2;
} else {
t = i;
}
if (i * 2 + 1 <= num) {
if (h[t] > h[i * 2 + 1]) {
t = i * 2 + 1;
}
}
if (t != i) {
int temp = h[t];
h[t] = h[i];
h[i] = temp;
i = t;
} else {
flag = 1;
}
}
}
}
堆排序的实现思路二：
1.创建大根堆 2.h[1]与h[n]交换 3.对h[1]向下调整, n-- 时间复杂度：O(N·logN)
Input: 14 99 5 36 2 19 1 46 12 7 22 25 28 17 92
Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99
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
87
88
89
90
91
92import java.util.Scanner;
public class heapPlus {
static int num, n = 0;
static int[] h = new int[15];
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
n = input.nextInt();
for (int i = 1; i <= n; i++) {
h[i] = input.nextInt();
}
num = n;
create();
heapsort();
for (int i = 1; i <= n; i++) {
System.out.print(h[i] + " ");
}
}
private static void heapsort() {
while (num > 1) {
int temp = h[num];
h[num] = h[1];
h[1] = temp;
num--;
siftdown(1);
}
}
private static void create() {
/**
* 从最后一个非叶结点到第1个结点向上调整
* */
for (int i = num / 2; i >= 1; i--) {
siftdown(i);
}
}
private static void siftup(int i) {
int flag = 0;
/**
* 堆顶
* */
if (i == 1) {
return;
}
while (i != 1 && flag == 0) {
/**
* 当前节点是否小于父结点
* */
if (h[i] > h[i/2]) {
int temp = h[i];
h[i] = h[i/2];
h[i/2] = temp;
} else {
flag = 1;
}
/**
* 向上调整
* */
i = i/2;
}
}
private static void siftdown(int i) {
int t, flag = 0;
while (i * 2 <= num && flag == 0) {
if (h[i] < h[i*2]) {
t = i * 2;
} else {
t = i;
}
if (i * 2 + 1 <= num) {
if (h[t] < h[i * 2 + 1]) {
t = i * 2 + 1;
}
}
if (t != i) {
int temp = h[t];
h[t] = h[i];
h[i] = temp;
i = t;
} else {
flag = 1;
}
}
}
}
堆是一种优先队列的数据结构 对于普通队列来说，在进行插入操作时比较方便，但是如果寻找队列中最大（或最小）的元素则时间复杂度较高； 对于已排序的数组来说，查找最大（或最小）元素并不在话下，但是插入元素则需要后面的元素整体后移，时间复杂度依旧很高。 而优先队列这种结构，则可以很好的解决上面的两种操作。 之前的Dijkstra算法就可以通过堆来进行优化。