-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStackSort.c
More file actions
70 lines (64 loc) · 1.47 KB
/
Copy pathStackSort.c
File metadata and controls
70 lines (64 loc) · 1.47 KB
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
/*
*
* @merge sort
* @O(nlgn)
* @max stack
* @int
*
*
*/
#include <stdio.h>
#include "inc/common.h"
#include "../include/StackSort.h"
#include <stdlib.h>
#define LEFT(i) (i >> 1)
#define RIGHT(i) ((i >> 1) + 1)
#define PARENT(i) iCEIL(i)
Stack* Creat() {
Stack* p = NULL;
p = (Stack*)malloc(sizeof(Stack));
if(p == NULL) {
printf("err : create stack failed");
return p;
}
p->size = 0;
return p;
}
// 将当前节点作为根节点，向下调整，以保持最大堆的特征
int _stack_down(Stack* p,int seq) {
int largest = seq;
int right = RIGHT(seq);
int left = LEFT(seq);
while(seq <= p->size) {
if(left <= p->size && p->stack[left - 1] > p->stack[largest - 1]) {
largest = left;
}
if(right <= p->size && p->stack[right - 1] > p->stack[largest - 1]) {
largest = right;
}
// 不需要调整
if(largest == seq) {
break;
}
SWAP(p->stack[largest - 1],p->stack[seq - 1]);
seq = largest;
}
return 0;
}
int BuildStack(Stack* p) {
int seq = 0;
for(seq = iFLOOR(p->size/2) ; seq > 0; seq --) {
_stack_down(p,seq);
}
}
int GetMax(Stack* p) {
int size = p->size;
// 堆头与堆尾交换
if(size > 0) {
SWAP(p->stack[0],p->stack[size - 1]);
p->size --;
// 从堆首向下调整
_stack_down(p,1);
}
return p->stack[size - 1];
}