其中递归函数fl_r1是仿照迭代版函数pop写的, 而fl_r是我自己写的,fl_r更优
x
// 节点范围[0, n)
typedef struct priority_queue {
int *data;
int size;
int cnt;
} priority_queue;
priority_queue *init(int n) { //初始化优先队列数组长度
priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
q->cnt = 0;
q->size = n;
q->data = (int *)malloc(sizeof(int) * n);
return q;
}
int insert(priority_queue *q, int val) { //大顶堆
if (q == NULL) return 0;
if (q->size == q->cnt) return 0; //堆满了
int n = ((q->cnt)++);
q->data[n] = val;
while (q->data[(n - 1) >> 1] < q->data[n] && n) { // < 大顶堆; > 小顶堆
//n为0时即q->cnt = 0, 即堆中只有一个数,无需比较
swap(q->data[n], q->data[(n - 1) >> 1]);
n = (n - 1) >> 1;
}
return 1;
}
int front(priority_queue *q) { // 取队列头部
return q->data[0];
}
int empty(priority_queue *q) { //队列判空
return q->cnt;
}
void output(priority_queue *q) {
if (q == NULL) return ;
for (int i = 0; i < q->cnt; i++) {
printf("%d ", q->data[i]);
}
return ;
}
//递归pop
void fl_r(priority_queue *q, int n, int l, int r) {
int nn = n, ll = l, rr = r;
if (ll >= q->cnt) return ;
if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
//output(q), printf("\n");
if (rr >= q->cnt) return ;
if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
// output(q), printf("\n");
fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
fl_r(q, ll, (ll << 1) + 1, (ll << 1) + 2);
return ;
}
//递归pop
void fl_r1(priority_queue *q, int n, int l, int r) {
int nn = n, ll = l, rr = r;
if (ll >= q->cnt) return ;
//if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
if (q->data[ll] > q->data[nn]) nn = ll;
//output(q), printf("\n");
if (rr >= q->cnt) return ;
// if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
if (q->data[rr] > q->data[nn]) nn = rr;
// output(q), printf("\n");
// fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
if (nn == n) return ;
swap(q->data[nn], q->data[n]);
n = nn;
fl_r1(q, nn, (nn << 1) + 1, (nn << 1) + 2);
return ;
}
int pop(priority_queue *q) {
if (!empty(q)) return 0;
if (q == NULL) return 0;
q->data[0] = q->data[--(q->cnt)];
// output(q), printf("\n");
fl_r(q, 0, 1, 2);
return 1;
}
void clear(priority_queue *q) {
if (q == NULL) return ;
free(q->data);
free(q);
return ;
}
int main() {
srand(time(0));
priority_queue *q = init(n);
for (int i = 0; i < n; i++) {
//int val = rand() % 1001;
printf("%s\n", insert(q, i) ? "插入成功" : "插入失败");
output(q);
printf("\n");
}
for (int i = 3; i < n; i++) {
printf("%s\n", pop(q) ? "删除成功" : "删除失败");
output(q);
printf("\n");
printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
}
clear(q);
return 0;
}
xxxxxxxxxx
// 节点范围[0, n)
typedef struct priority_queue {
int *data;
int size;
int cnt;
} priority_queue;
priority_queue *init(int n) { //初始化优先队列数组长度
priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
q->cnt = 0;
q->size = n;
q->data = (int *)malloc(sizeof(int) * n);
return q;
}
// 数据范围[0, n)
int push(priority_queue *q, int val) { //大顶堆
if (q == NULL) return 0;
if (q->size == q->cnt) return 0; //堆满了
int n = ((q->cnt)++);
q->data[n] = val;
while (n && q->data[(n - 1) >> 1] < q->data[n]) { // < 大顶堆; > 小顶堆
//n为0时即q->cnt = 0, 即堆中只有一个数,无需比较
swap(q->data[n], q->data[(n - 1) >> 1]);
n = (n - 1) >> 1;
}
return 1;
}
int front(priority_queue *q) { // 取队列头部
return q->data[0];
}
int empty(priority_queue *q) { //队列判空
return q->cnt;
}
void output(priority_queue *q) {
if (q == NULL) return ;
for (int i = 0; i < q->cnt; i++) {
printf("%d ", q->data[i]);
}
return ;
}
//迭代版pop
int pop_(priority_queue *q) {
if (q == NULL) return 0;
if (!empty(q)) return 0;
q->data[0] = q->data[--(q->cnt)];
int ind = 0;
//max_root 为一个三元组中最大值的序号
//优先队列在二叉树种保证了对于每棵子树,其根节点都是最大值
//自上而下求出 完美二叉树 最大值
while (((ind << 1) + 1) < (q->cnt)) {
int max_root = ind, l = (ind << 1) + 1, r = (ind << 1) + 2;
if (r < q->cnt && q->data[max_root] < q->data[r]) max_root = r; //与右节点比较, 取最大值
if (q->data[max_root] < q->data[l]) max_root = l; //与左节点比较, 取最大值
if (max_root == ind) break;
swap(q->data[ind], q->data[max_root]);
ind = max_root;
}
return 1;
}
void clear(priority_queue *q) {
if (q == NULL) return ;
free(q->data);
free(q);
return ;
}
int main() {
srand(time(0));
priority_queue *q = init(n);
for (int i = 0; i < n; i++) {
//int val = rand() % 1001;
printf("%s\n", push(q, i) ? "插入成功" : "插入失败");
output(q);
printf("\n");
}
for (int i = 3; i < n; i++) {
printf("%s\n", pop_(q) ? "删除成功" : "删除失败");
output(q);
printf("\n");
// printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
}
clear(q);
return 0;
}
xxxxxxxxxx
// 节点范围[0, n)
typedef struct priority_queue {
int *data;
int size; //代表队列长度
int cnt; //代表存在元素个数
} priority_queue;
priority_queue *init(int n) { //初始化优先队列数组长度
priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
q->data = (int *)malloc(sizeof(int) * (n + 1));
q->cnt = 0;
q->size = n;
return q;
}
int top(priority_queue *q) { // 取队列头部
return q->data[1];
}
int empty(priority_queue *q) { //队列判空
return q->cnt == 0;
}
void output(priority_queue *q) {
if (q == NULL) return ;
for (int i = 1; i <= q->cnt; i++) {
printf("%d ", q->data[i]);
}
return ;
}
int push(priority_queue *q, int val) { //大顶堆
if (q == NULL) return 0;
if (q->size == q->cnt) return 0; //堆满了
q->data[++(q->cnt)] = val;
int n = q->cnt;
while (n >> 1 && q->data[n] > q->data[n >> 1]) { // < 大顶堆; > 小顶堆
swap(q->data[n], q->data[n >> 1]);
n >>= 1;
}
return 1;
}
//迭代版pop
int pop(priority_queue *q) {
if (q == NULL) return 0;
if (empty(q)) return 0;
q->data[1] = q->data[(q->cnt)--];
// output(q), printf("\n");
int ind = 1;
//max_root 为一个三元组中最大值的序号
//优先队列在二叉树种保证了对于每棵子树,其根节点都是最大值
//自上而下求出 完美二叉树 最大值
while ((ind << 1) <= q->cnt) {
int max_root = ind, l = ind << 1, r = ind << 1 | 1;
if (q->data[max_root] < q->data[l]) max_root = l; //与左节点比较, 取最大值
// 如果它有右节点 ; r <= q->cnt 和 q->data[max_root] < q->data[r]顺序不能变
if (r <= q->cnt && q->data[max_root] < q->data[r]) max_root = r; //与右节点比较, 取最大值
if (max_root == ind) break;
swap(q->data[ind], q->data[max_root]);
ind = max_root;
// output(q), printf("\n");
}
return 1;
}
void clear(priority_queue *q) {
if (q == NULL) return ;
free(q->data);
free(q);
return ;
}
int main() {
srand(time(0));
priority_queue *q = init(n);
for (int i = 0; i < n; i++) {
//int val = rand() % 1001;
push(q, i);
printf("插入%d到堆中\n", i);
output(q), printf("\n");
}
//output(q), printf("\n");
for (int i = 3; i < n; i++) {
printf("%s\n", pop(q) ? "删除成功" : "删除失败");
output(q);
printf("\n");
// printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
}
clear(q);
return 0;
}
xxxxxxxxxx
// 节点范围[1, n]
typedef struct priority_queue {
int *data;
int size; //代表队列长度
int cnt; //代表存在元素个数
} priority_queue;
priority_queue *init(int n) { //初始化优先队列数组长度
priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
q->data = (int *)malloc(sizeof(int) * (n + 1));
q->cnt = 0;
q->size = n;
return q;
}
int top(priority_queue *q) { // 取队列头部
return q->data[1];
}
int empty(priority_queue *q) { //队列判空
return q->cnt == 0;
}
void output(priority_queue *q) {
if (q == NULL) return ;
for (int i = 1; i <= q->cnt; i++) {
printf("%d ", q->data[i]);
}
return ;
}
int push(priority_queue *q, int val) { //大顶堆
if (q == NULL) return 0;
if (q->size == q->cnt) return 0; //堆满了
q->data[++(q->cnt)] = val;
int n = q->cnt;
while (n >> 1 && q->data[n] > q->data[n >> 1]) { // < 大顶堆; > 小顶堆
swap(q->data[n], q->data[n >> 1]);
n >>= 1;
}
return 1;
}
//递归pop
void fl_r(priority_queue *q, int n, int l, int r) {
int nn = n, ll = l, rr = r;
if (ll > q->cnt) return ;
//if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
if (q->data[ll] > q->data[nn]) nn = ll;
//output(q), printf("\n");
if (rr > q->cnt) return ;
// if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
if (q->data[rr] > q->data[nn]) nn = rr;
// output(q), printf("\n");
// fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
if (nn == n) return ;
swap(q->data[nn], q->data[n]);
n = nn;
fl_r(q, nn, nn << 1, (nn << 1) | 1);
return ;
}
int pop(priority_queue *q) {
if (q == NULL) return 0;
if (empty(q)) return 0;
q->data[1] = q->data[(q->cnt)--];
// output(q), printf("\n");
fl_r(q, 1, 2, 3);
return 1;
}
void clear(priority_queue *q) {
if (q == NULL) return ;
free(q->data);
free(q);
return ;
}
int main() {
srand(time(0));
priority_queue *q = init(n);
for (int i = 0; i < n; i++) {
//int val = rand() % 1001;
push(q, i);
printf("插入%d到堆中\n", i);
output(q), printf("\n");
}
//output(q), printf("\n");
for (int i = 3; i < n; i++) {
printf("%s\n", pop(q) ? "删除成功" : "删除失败");
output(q);
printf("\n");
// printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
}
clear(q);
return 0;
}