Implement the min-max heap using c++ code.

以下是 C 代码实现的最小最大堆：

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

#define MAX_SIZE 100

typedef struct {
  int* arr;
  int size;
  int capacity;
} MinMaxHeap;

void swap(MinMaxHeap* heap, int i, int j) {
  int temp = heap->arr[i];
  heap->arr[i] = heap->arr[j];
  heap->arr[j] = temp;
}

void trickle_down(MinMaxHeap* heap, int i, int is_min) {
  int child1 = 2 * i + 1;
  int child2 = 2 * i + 2;

  int max_child = child1;
  if (child2 < heap->size && heap->arr[child2] > heap->arr[child1]) {
    max_child = child2;
  }

  int min_child = child1;
  if (child2 < heap->size && heap->arr[child2] < heap->arr[child1]) {
    min_child = child2;
  }

  int extreme_child = is_min ? min_child : max_child;
  if (extreme_child < heap->size && heap->arr[extreme_child] >
      heap->arr[i]) {
    swap(heap, i, extreme_child);
    trickle_down(heap, extreme_child, !is_min);
  }
}

void trickle_up(MinMaxHeap* heap, int i, int is_min) {
  int parent = (i - 1) / 2;

  if (parent < 0 || parent == i) {
    return;
  }

  if ((!is_min && heap->arr[i] > heap->arr[parent]) ||
      (is_min && heap->arr[i] < heap->arr[parent])) {
    swap(heap, i, parent);
    trickle_up(heap, parent, !is_min);
  }
}

void build_heap(MinMaxHeap* heap, int* arr, int size) {
  heap->arr = arr;
  heap->size = size;
  heap->capacity = size;

  for (int i = size / 2 - 1; i >= 0; i--) {
    trickle_down(heap, i, i == 0);
  }
}

void insert(MinMaxHeap* heap, int value) {
  if (heap->size == heap->capacity) {
    return;
  }

  heap->arr[heap->size] = value;
  trickle_up(heap, heap->size, heap->size % 2 == 1);
  heap->size++;
}

int remove_root(MinMaxHeap* heap) {
  if (heap->size == 0) {
    return -1;
  }

  int root = heap->arr[0];
  swap(heap, 0, heap->size - 1);
  heap->size--;

  trickle_down(heap, 0, 1);
  return root;
}

void print_heap(MinMaxHeap* heap) {
  for (int i = 0; i < heap->size; i++) {
    printf("%d ", heap->arr[i]);
  }
  printf("\n");
}

void test_heap() {
  MinMaxHeap heap;
  int arr[MAX_SIZE];

  for (int i = 1; i <= 15; i++) {
    insert(&heap, i);
  }

  printf("Initial heap: ");
  print_heap(&heap);

  for (int i = 1; i <= 5; i++) {
    int root = remove_root(&heap);
    printf("Removed root: %d, new heap: ", root);
    print_heap(&heap);
  }

  printf("Adding elements 16-20: ");
  for (int i = 16; i <= 20; i++) {
    insert(&heap, i);
  }
  print_heap(&heap);

  printf("Removing all elements: ");
  while (heap.size > 0) {
    int root = remove_root(&heap);
    printf("%d ", root);
  }
  printf("\n");
}

int main() {
  test_heap();
  return 0;
}

在此实现中，最小最大堆用一维数组表示，其节点按照从左到右、从上到下的顺序编号。实现使用了两个递归函数 `trickle_down()` 和 `trickle_up()` 来维护堆的顺序性，当插入或删除元素时，需要使用这两个函数来重新组织堆。

在创建和打印最小最大堆时，使用了 `build_heap()` 和 `print_heap()` 函数。在该实现中，最小最大堆在递归堆时与它在 `arr[]` 数组中的位置有关系。这些关系是：

- 一个节点的左子节点位于 `2*i+1` 处，右子节点位于 `2*i+2` 处。
- 一个节点的父节点位于 `(i-1)/2` 处。

此外，由于最小最大堆每个节点都可以有 2 或 3 个子节点，因此需要在 `trickle_down()` 和 `trickle_up()` 函数中考虑这个特殊情况。