AB18. 【模板】堆
描述
请你实现一个堆(大根堆)。操作：
push x：将
top：输出堆顶元素。若堆为空，输出"empty"(不含引号)。
pop：输出堆顶元素，且弹出堆顶。若堆为空，输出"empty"(不含引号)。
输入描述
第一行输入一个整数接下来的
输出描述
按对应操作要求输出。示例1
输入:
11 push 1 top push 3 top push 2 top pop pop pop top pop
输出:
1 3 3 3 2 1 empty empty
AB18. 【模板】堆
描述
请你实现一个堆(大根堆)。输入描述
第一行输入一个整数输出描述
按对应操作要求输出。示例1
输入:
11 push 1 top push 3 top push 2 top pop pop pop top pop
输出:
1 3 3 3 2 1 empty empty
C++ 解法, 执行用时: 21ms, 内存消耗: 1420KB, 提交时间: 2022-06-19
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Heap {
int array[1024*100];
int size;
int capacity;
} Heap;
void heap_create(Heap *p)
{
memset(p->array, 0x00, sizeof(p->array));
p->capacity = 1024*100;
p->size = 0;
}
void heap_adjust_down(int *a, int n, int parent)
{
int child = 2 * parent;
int t;
while(child < n)
{
if(child + 1 < n && a[child] < a[child+1])
{
child++;
}
if(a[child] > a[parent])
{
t = a[child];
a[child] = a[parent];
a[parent] = t;
parent = child;
child = 2 * parent;
}
else
{
break;
}
}
}
void heap_adjust_up(int *a, int n, int child)
{
int parent = (child) / 2;
int t;
while(child > 0)
{
if(a[child] > a[parent])
{
t = a[child];
a[child] = a[parent];
a[parent] = t;
child = parent;
parent = (child) / 2;
}
else
{
break;
}
}
}
void heap_push(Heap *p, int x)
{
p->array[p->size] = x;
p->size++;
heap_adjust_up(p->array, p->size, p->size-1);
}
int heap_top(Heap *p)
{
return p->array[0];
}
int heap_pop(Heap *p)
{
int c = p->array[0];
p->array[0] = p->array[p->size-1];
p->array[p->size-1] = 0;
p->size--;
heap_adjust_down(p->array, p->size, 0);
return c;
}
int main()
{
Heap heap;
char cmd[64];
int n;
int t;
int i;
heap_create(&heap);
scanf("%d", &n);
for(i=0; i<n+1; i++)
{
memset(cmd, 0x00, sizeof(cmd));
fgets(cmd, 63, stdin);
if(strncmp(cmd, "push", 4) == 0)
{
t = atoi(cmd+5);
heap_push(&heap, t);
}
else if(strncmp(cmd, "pop", 3) == 0)
{
if(heap.size != 0)
{
t = heap_pop(&heap);
printf("%d\n", t);
}
else
{
printf("empty\n");
}
}
else if(strncmp(cmd, "top", 3) == 0)
{
if(heap.size != 0)
{
t = heap_top(&heap);
printf("%d\n", t);
}
else
{
printf("empty\n");
}
}
}
return 0;
}
C 解法, 执行用时: 23ms, 内存消耗: 1536KB, 提交时间: 2022-06-03
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Heap {
int array[1024*100];
int size;
int capacity;
} Heap;
void heap_create(Heap *p)
{
memset(p->array, 0x00, sizeof(p->array));
p->capacity = 1024*100;
p->size = 0;
}
void heap_adjust_down(int *a, int n, int parent)
{
int child = 2 * parent;
int t;
while(child < n)
{
if(child + 1 < n && a[child] < a[child+1])
{
child++;
}
if(a[child] > a[parent])
{
t = a[child];
a[child] = a[parent];
a[parent] = t;
parent = child;
child = 2 * parent;
}
else
{
break;
}
}
}
void heap_adjust_up(int *a, int n, int child)
{
int parent = (child) / 2;
int t;
while(child > 0)
{
if(a[child] > a[parent])
{
t = a[child];
a[child] = a[parent];
a[parent] = t;
child = parent;
parent = (child) / 2;
}
else
{
break;
}
}
}
void heap_push(Heap *p, int x)
{
p->array[p->size] = x;
p->size++;
heap_adjust_up(p->array, p->size, p->size-1);
}
int heap_top(Heap *p)
{
return p->array[0];
}
int heap_pop(Heap *p)
{
int c = p->array[0];
p->array[0] = p->array[p->size-1];
p->array[p->size-1] = 0;
p->size--;
heap_adjust_down(p->array, p->size, 0);
return c;
}
int main()
{
Heap heap;
char cmd[64];
int n;
int t;
int i;
heap_create(&heap);
scanf("%d", &n);
for(i=0; i<n+1; i++)
{
memset(cmd, 0x00, sizeof(cmd));
fgets(cmd, 63, stdin);
if(strncmp(cmd, "push", 4) == 0)
{
t = atoi(cmd+5);
heap_push(&heap, t);
}
else if(strncmp(cmd, "pop", 3) == 0)
{
if(heap.size != 0)
{
t = heap_pop(&heap);
printf("%d\n", t);
}
else
{
printf("empty\n");
}
}
else if(strncmp(cmd, "top", 3) == 0)
{
if(heap.size != 0)
{
t = heap_top(&heap);
printf("%d\n", t);
}
else
{
printf("empty\n");
}
}
}
return 0;
}
C++ 解法, 执行用时: 25ms, 内存消耗: 1032KB, 提交时间: 2022-04-27
#include <bits/stdc++.h>
using namespace std;
#define maxn 100000+10
#define llo long long
llo a[maxn];
llo len;
void up(int x)
{
int p = x/2;
if(p==0) return;
if(a[x]>a[p])
{
swap(a[x], a[p]);
up(p);
}
}
void down(int x)
{
int l = 2*x;
int r=l+1;
if(l>len)return ;
if(r<=len)
{
if(a[x]<a[l]&& a[l]>a[r])
{
swap(a[x],a[l]);
down(l);
}
else if(a[x]<a[r]&&a[r]>a[l])
{
swap(a[x],a[r]);
down(r);
}
}
else
{
if(a[x]<a[l])
{
swap(a[x],a[l]);
down(l);
}
}
}
int main()
{
llo t,x;
scanf("%lld",&t);
char s[10];
len=0;
for(int i=0;i<t;i++)
{
scanf("%s",s);
if(s[0]=='p'&&s[1]=='u')
{
scanf("%lld",&x);
a[++len] =x;
up(len);
}
else if(s[0]=='p'&&s[1]=='o')
{
if(len)
{
printf("%lld\n",a[1]);
a[1] = a[len];
len--;
down(1);
}
else
printf("empty\n");
}
else
{
if(len)
printf("%lld\n",a[1]);
else
printf("empty\n");
}
}
}
C 解法, 执行用时: 30ms, 内存消耗: 1024KB, 提交时间: 2022-06-17
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<limits.h>
void shiftdown(int* heap,int index,int* count){
int k = 2*index + 1;
while(k<(*count)){
if(k+1<count && heap[k] < heap[k+1])k++;
if(heap[index]<heap[k]){
int temp = heap[index];
heap[index] = heap[k];
heap[k] = temp;
index = k;
}
else{
break;
}
k = 2*k + 1;
}
}
void pop(int* heap,int* count){
heap[0] = heap[(*count)-1];
heap[(*count)-1] = INT_MIN;
(*count)--;
shiftdown(heap,0,count);
}
void shiftup(int* heap,int index){
while(index>0 && heap[index]>heap[(index-1)/2]){
int temp = heap[index];
heap[index] = heap[(index-1)/2];
heap[(index-1)/2] = temp;
index = (index-1)/2;
}
}
void insert(int* heap, int value,int* count){
heap[*count] = value;
(*count)++;
shiftup(heap,(*count)-1);
}
int main(){
int count = 0;
int n = 0;
scanf("%d",&n);
int* heap = (int*)calloc(n,sizeof(int));
char cmd[10] = {0};
char num[10] = {0};
while(n--){
scanf("%s",cmd);
if(!strcmp(cmd,"push")){
scanf("%s",num);
insert(heap,atoi(num),&count);
}
else if(!strcmp(cmd,"pop")){
if(count){
printf("%d\n",heap[0]);
pop(heap,&count);
}
else{
printf("empty\n");
}
}
else{
if(count){
printf("%d\n",heap[0]);
}
else{
printf("empty\n");
}
}
}
return 0;
}
C 解法, 执行用时: 32ms, 内存消耗: 1016KB, 提交时间: 2022-07-14
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// back指向最后一位元素
// front指向首元素
// 大根堆的封装
typedef struct {
int arr[100000];
int front;
int back;
} heap;
void sink(heap *h) {
int parent = 0;
while (parent * 2 + 1 <= h->back) {
int child = parent * 2 + 1;
if (child + 1 <= h->back && h->arr[child + 1] > h->arr[child]) {
++child;
}
if (h->arr[parent] > h->arr[child]) {
break;
}
int tmp = h->arr[parent];
h->arr[parent] = h->arr[child];
h->arr[child] = tmp;
parent = child;
}
}
void rise(heap *h) {
int child = h->back;
while (child > 0) {
int parent = (child - 1) / 2;
if (h->arr[parent] > h->arr[child]) {
break;
} else {
int tmp = h->arr[child];
h->arr[child] = h->arr[parent];
h->arr[parent] = tmp;
child = parent;
}
}
}
void push(heap *h, int x) {
h->arr[++(h->back)] = x;
rise(h);
}
int top(heap *h) {
if (h->back != -1) {
return h->arr[h->front];
} else {
printf("empty\n");
return -1;
}
}
void pop(heap *h) {
if (h->back != -1) {
printf("%d\n", h->arr[h->front]);
h->arr[h->front] = h->arr[(h->back)--];
sink(h);
} else {
printf("empty\n");
}
}
int main(int argc, char *argv[]) {
heap *h = (heap *)malloc(sizeof(heap));
h->front = 0;
h->back = -1;
int count = 0;
scanf("%d", &count);
while (--count >= 0) {
char str[5];
scanf("%s", str);
if (!strcmp(str, "push")) {
int tmp;
scanf("%d", &tmp);
push(h, tmp);
} else if (!strcmp(str, "top")) {
int tmp = top(h);
if (tmp != -1) {
printf("%d\n", tmp);
}
} else if (!strcmp(str, "pop")) {
pop(h);
}
}
free(h);
return 0;
}