C语言每日练习之二叉堆

什么是二叉堆？

二叉堆是一种特殊的二叉树，它满足两个特性：

1. 堆的父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值；
2. 堆总是一棵完全二叉树。

实现二叉堆

数据结构

为了实现二叉堆，我们需要先定义数据结构。二叉堆常常使用数组来表示，数组中第一个元素一般为根节点，其余元素依次为树中其它节点的值。通过数组下标计算节点间的关系，可以快速地访问堆中的元素。

typedef struct 
{
  int* array;     // 指向堆的数组
  int count;      // 堆中元素的数量
  int capacity;   // 堆的容量，即最多可以存储多少个元素
} Heap;

创建二叉堆

我们可以使用自上而下或自下而上两种方式创建二叉堆。这里我们讲下自下而上的方法，从最后一个非叶子节点开始。假设当前节点的下标是i，其父节点的下标为(i-1)/2，左右子节点的下标为2*i+1和2*i+2，那么可以用下面的代码创建一个二叉堆。

void buildHeap(Heap* heap, int* array, int count)
{
  // 将数组复制到堆中，注意下标从0开始
  memcpy(heap->array, array, count * sizeof(int));
  heap->count = count;
  heap->capacity = count;

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

插入元素

在向堆中插入元素时，我们可以将其插到数组的尾部，并沿着其父节点和祖先节点逐步上移，以保持堆的特性。

void insert(Heap* heap, int data)
{
  assert(heap->count < heap->capacity);

  heap->array[heap->count] = data;
  heap->count++;

  int i = heap->count - 1;
  while (i > 0 && heap->array[(i - 1) / 2] < heap->array[i])
  {
    swap(&heap->array[(i - 1) / 2], &heap->array[i]);
    i = (i - 1) / 2;
  }
}

弹出堆顶元素

在弹出堆顶元素时，我们可以取出根节点，并将堆尾的元素放到根节点的位置，然后沿着其子节点逐步下移，以保持堆的特性。

int pop(Heap* heap)
{
  assert(heap->count > 0);

  int max_value = heap->array[0];
  heap->count--;

  heap->array[0] = heap->array[heap->count];
  shiftDown(heap, 0);

  return max_value;
}

下移元素

在下移元素时，我们可以将其与其两个子节点中较大的一个比较，如果小于子节点的值，则交换位置，继续向下比较。这样可以确保每次下移时，选择的都是当前节点和子节点中最大的那个，从而保证堆的特性不变。

void shiftDown(Heap* heap, int i)
{
  int max = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < heap->count && heap->array[left] > heap->array[max])
  {
    max = left;
  }

  if (right < heap->count && heap->array[right] > heap->array[max])
  {
    max = right;
  }

  if (max != i)
  {
    swap(&heap->array[i], &heap->array[max]);
    shiftDown(heap, max);
  }
}

示例说明

示例一：使用二叉堆来进行堆排序

假设我们有一个数组int array[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};，我们可以使用一个二叉堆来排序这个数组。首先将数组中的元素插入到二叉堆中，然后反复弹出堆顶元素。按照从大到小（或从小到大）的顺序，输出弹出的元素即为排好序的数组。

void heapSort(int* array, int count)
{
  Heap heap;
  heap.array = (int*)malloc(count * sizeof(int));
  heap.count = 0;
  heap.capacity = count;

  for (int i = 0; i < count; i++)
  {
    insert(&heap, array[i]);
  }

  for (int i = count - 1; i >= 0; i--)
  {
    array[i] = pop(&heap);
  }

  free(heap.array);
}

示例二：求一个数组中第k大的元素

假设我们有一个数组int array[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};，我们想要求出其中第5大的元素。我们可以使用一个小根堆来维护前k大的元素（假设我们维护的是前k大的元素，那么堆的容量为k），将数组中的元素逐个插入到堆中，如果堆中元素的数量大于k，就弹出堆顶元素。当插入完所有的元素后，堆顶元素即为第k大的元素。

int findKthLargest(int* array, int count, int k)
{
  Heap heap;
  heap.array = (int*)malloc(k * sizeof(int));
  heap.count = 0;
  heap.capacity = k;

  for (int i = 0; i < count; i++)
  {
    if (heap.count < k)
    {
      insert(&heap, array[i]);
    }
    else if (array[i] > heap.array[0])
    {
      heap.array[0] = array[i];
      shiftDown(&heap, 0);
    }
  }

  int result = heap.array[0];
  free(heap.array);

  return result;
}