题解 | #大根堆（模板）#

C语言版本实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//  back指向最后一位元素
//  front指向首元素
//  大根堆的封装
typedef struct {
  int arr[100000];
  int front;
  int back;
} heap;

//  排序
// for (int i = (h->back - 1) / 2; i >= 0; --i) {
//   sink(i);
// }

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;
}