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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145 | #include <stdio.h>
#include <stdlib.h>
#define MIN -1000000 //定义最小的优先级
//最大优先级队列实现后进先出栈：1.利用最大堆实现最大优先队列，2.利用最大优先队列实现栈，进栈的元素优先级递增
typedef struct Node {
int elem; //储存栈中的元素值
int key; //为每一个进栈的元素赋一个优先级值
} Node;
typedef struct Stack {
int length; //栈的长度
Node *data; //栈中的元素
} Stack;
/*************************************Part1.利用最大堆实现最大优先队列*************************************/
void swap(Node *a, Node *b) { //交换元素a与元素b
Node tmp;
tmp.elem = (*a).elem;
tmp.key = (*a).key;
(*a).elem = (*b).elem;
(*a).key = (*b).key;
(*b).elem = tmp.elem;
(*b).key = tmp.key;
}
void max_heapify(Node *a, int size, int i) { //使元素的优先级满足最大堆的性质
int left = 2 * i; //i的左孩子
int right = 2 * i + 1; //i的右孩子
int largest; //选出具有最大优先级的元素，下标存在largest中
if (left <= size && a[left].key > a[i].key) {
largest = left;
}
else {
largest = i;
}
if (right <= size && a[right].key > a[largest].key) {
largest = right;
}
if (largest != i) { //具有最大优先级的元素是i的某个孩子结点
swap(&a[i], &a[largest]);
max_heapify(a, size, largest); //递归调用
}
}
void build_max_heap(Node *a, int size) { //构建最大堆
int i;
for(i = size / 2; i >= 1; i--) {
max_heapify(a, size, i);
}
}
Node heap_maximum(Node *a) { //返回最大优先级队列中优先级最大的元素，即最大堆的顶
return a[1];
}
void heap_increase_key(Node *a, int i, int key) { //将元素a[i]的优先级增加到 key
if (key < a[i].key) {
printf("New key is smaller than current key!(Error from heap_increase_key)\n");
exit(0);
}
a[i].key = key;
while (i > 1 && a[i / 2].key < a[i].key) {
swap(&a[i], &a[i / 2]);
i = i / 2;
}
}
Node heap_extract_max(Node *a, int *size) { //去掉并返回最大优先队列中具有最大优先级的元素
if (*size < 1) {
printf("Heap underflow!(Error from heap_extract_max)\n");
exit(-1);
}
Node max = a[1];
a[1] = a[*size];
(*size)--;
max_heapify(a, *size, 1);
return max;
}
void max_heap_insert(Node *a, int *size, int key, int elem) { //向最大优先队列中插入元素，即扩展最大堆
(*size)++;
a[*size].key = MIN;
a[*size].elem = elem;
heap_increase_key(a, *size, key);
}
/************************************************Part1 ends************************************************/
/*************************************Part2.利用最大优先队列实现栈操作*************************************/
bool is_stack_empty(Stack *s) { //判断栈是否为空
if ((*s).length == 0) return true;
return false;
}
void stack_push(Stack *s, int elem) { //入栈
Node *old = (*s).data;
(*s).data = (Node *)malloc(((*s).length + 2) * sizeof(Node)); //开创新的空间
int i;
for (i = 1; i <= (*s).length; i++) {
(*s).data[i] = old[i];
}
free(old); //释放旧的空间
max_heap_insert(s->data, &s->length, s->length + 1, elem);
}
int stack_getTop(Stack *s) { //获取栈顶元素
return heap_maximum(s->data).elem;
}
int stack_pop(Stack *s) { //出栈
return heap_extract_max(s->data, &s->length).elem;
}
int main() {
Stack s;
printf("Input the length of the stack:\n");
scanf("%d", &s.length);
s.data = (Node *)malloc((s.length + 1) * sizeof(Node));
printf("Input the element:\n");
int i;
for(i = 1; i <= s.length; i++){
s.data[i].key = i;
scanf("%d", &s.data[i].elem);
}
printf("Build the heap for the stack!\n");
build_max_heap(s.data, s.length);
printf("The result of the heap:\n");
for(i = 1; i <= s.length; i++)
printf("%d(Priority:%d) ", s.data[i].elem, s.data[i].key);
printf("\n");
int push_elem;
printf("Input the element you want to push into the stack:\n");
scanf("%d", &push_elem);
stack_push(&s, push_elem);
printf("Now the top of the stack is: %d\n", stack_getTop(&s));
printf("Output the stack:\n");
while (!is_stack_empty(&s)) {
printf("pop: %d\n", stack_pop(&s));
}
return 0;
}
|