最小堆二叉树是二叉树，其中根节点在树中具有最小密钥。

上面的定义对于树中的所有子树都适用。
这称为"最小堆"属性。

除了最后两层以外，几乎每个节点都必须有两个子节点。
也就是说，除了最后两层外，这几乎是完整的二叉树。

由于上面的两个属性成立，因此下面的树是最小堆二叉树的示例。

最小堆树

既然我们已经介绍了最小堆树，那么让我们看一下如何表示它。

最小堆树的表示

最小堆二叉树通常表示为数组，并根据以下格式进行索引：

整个树的根在arr [0]。

我们将使用下图所示的索引。
您可以在此处找到与上表相匹配的模式，这一点并不难。

最小堆二叉树索引

该索引遵循二进制树的级别顺序遍历，因此二进制堆数组是使用级别顺序遍历的二进制树。

最小堆数组

上图显示了最小堆树的数组表示形式。

现在，我们已经涵盖了这些概念，让我们继续使用C来实现它！

实施最小堆树

我们将使用数组表示法来构建树。
让我们开始编写Min Heap的结构。

typedef struct MinHeap MinHeap;
struct MinHeap {
  int* arr;
  //Current Size of the Heap
  int size;
  //Maximum capacity of the heap
  int capacity;
};

我们将有一个元素数组和一个大小，该大小会随着元素的插入或者删除而更新。

该阵列还具有容量，该容量指示阵列的最大大小。

我们需要编写一些函数来表示我们正在代表最小堆树，例如查找父级和子级。

int parent(int i) {
  //Get the index of the parent
  return (i - 1)/2;
}

int left_child(int i) {
  return (2*i + 1);
}

int right_child(int i) {
  return (2*i + 2);
}

int get_min(MinHeap* heap) {
  //Return the root node element,
  //since that's the minimum, by the min-heap
  //property
  return heap->arr[0];
}

我们将编写函数来初始化和释放堆。

MinHeap* init_minheap(int capacity) {
  MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
  minheap->arr = (int*) calloc (capacity, sizeof(int));
  minheap->capacity = capacity;
  minheap->size = 0;
  return minheap;
}

void free_minheap(MinHeap* heap) {
  if (!heap)
      return;
  free(heap->arr);
  free(heap);
}

讲完这些后，我们现在继续介绍如何插入元素！

插入最小堆

插入算法很简单。
这会将元素插入树中。

分解算法：

• 首先，始终将其插入树的底部。
  插入元素的初始位置在最后一层。

• 现在，我们将需要更新此元素的位置，以便满足min-heap属性。

• 由于每个子树的根节点必须最小，因此请检查其直接父级的子树。

• 如果父级大于此插入的元素，则需要通过交换来更新其位置。

• 但是我们还没有完成，因为min-heap属性可能会违反更新后的节点的子树！

• 我们需要继续交换，直到到达根节点为止。

要了解此过程，请举一个例子。

考虑下面的树，它只有一个元素。

最小堆一元素

让我们插入元素40。
由于只有一个元素，所以它插入到底部，并且我们观察到min-heap属性满足，因为10 <40。
因此不需要交换。

最小堆两个元素

接下来，我们将插入50。
执行类似的步骤。

最小堆三要素

接下来，我们将插入5。
因此，现在，我们首先在树的底部插入索引3。

最小堆状态

对于子树1-3，因此对于整个树，都违反了min heap属性。
因此，我们必须继续与父交换，直到到达根为止。

交换

因此，我们需要再进行一次交换，因为同样，对于以节点0为根的子树，min-heap属性被违反了。

交换后最小堆

好的。
现在我们已经可视化了，让我们写下来吧！

MinHeap* insert_minheap(MinHeap* heap, int element) {
  //Inserts an element to the min heap
  //We first add it to the bottom (last level)
  //of the tree, and keep swapping with it's parent
  //if it is lesser than it. We keep doing that until
  //we reach the root node. So, we will have inserted the
  //element in it's proper position to preserve the min heap property
  if (heap->size == heap->capacity) {
      fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
      return heap;
  }
  //We can add it. Increase the size and add it to the end
  heap->size++;
  heap->arr[heap->size - 1] = element;

  //Keep swapping until we reach the root
  int curr = heap->size - 1;
  //As long as you aren't in the root node, and while the 
  //parent of the last element is greater than it
  while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
      //Swap
      int temp = heap->arr[parent(curr)];
      heap->arr[parent(curr)] = heap->arr[curr];
      heap->arr[curr] = temp;
      //Update the current index of element
      curr = parent(curr);
  }
  return heap; 
}

现在，我们将实现删除方法。

从最小堆中删除

在考虑删除任何索引元素之前，由于min-heap与根紧密相关，因此我们将首先考虑删除根。

要删除最小元素(即根)，我们将执行以下操作：

• 将根更新为数组(树)的最后一个元素

• 现在，我们将删除底部的最后一个元素。
  这类似于最后交换和删除！只是因为我们不再关心根值，我们才更新它。

• 再次出现的问题是，我们需要维护min-heap属性。

• 因此，我们必须确保整个树都保留此属性。
  我们将使用一个名为" heapify()"的函数为我们完成此任务。

因此，我们知道删除方法也将在完成heapify()方法之后完成。

MinHeap* delete_minimum(MinHeap* heap) {
  //Deletes the minimum element, at the root
  if (!heap || heap->size == 0)
      return heap;

  int size = heap->size;
  int last_element = heap->arr[size-1];
  
  //Update root value with the last element
  heap->arr[0] = last_element;

  //Now remove the last element, by decreasing the size
  heap->size--;
  size--;

  //We need to call heapify(), to maintain the min-heap
  //property
  heap = heapify(heap, 0);
  return heap;
}

heapify()过程

该函数通过交换其直接子树的最小元素来获取元素索引" index"，并维护最小堆属性。

生成的树将满足min-heap属性。

这涉及找到子树的最小元素，并与当前元素进行交换。

此后，我们仍然需要确保整个树都满足此要求。
因此，我们需要递归地调用最小元素上的过程，直到到达根为止！

MinHeap* heapify(MinHeap* heap, int index) {
  //Rearranges the heap as to maintain
  //the min-heap property
  if (heap->size <= 1)
      return heap;
  
  int left = left_child(index); 
  int right = right_child(index); 

  //Variable to get the smallest element of the subtree
  //of an element an index
  int smallest = index; 
  
  //If the left child is smaller than this element, it is
  //the smallest
  if (left < heap->size && heap->arr[left] < heap->arr[index]) 
      smallest = left; 
  
  //Similarly for the right, but we are updating the smallest element
  //so that it will definitely give the least element of the subtree
  if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
      smallest = right; 

  //Now if the current element is not the smallest,
  //swap with the current element. The min heap property
  //is now satisfied for this subtree. We now need to
  //recursively keep doing this until we reach the root node,
  //the point at which there will be no change!
  if (smallest != index) 
  { 
      int temp = heap->arr[index];
      heap->arr[index] = heap->arr[smallest];
      heap->arr[smallest] = temp;
      heap = heapify(heap, smallest); 
  }

  return heap;
}

现在我们可以扩展这个delete_minimum()函数，以删除任何元素。

删除任意元素

这仅涉及将所需元素设置为可能的最小值，即get_min()-1，因为它必须小于当前的最小值。

现在，我们将继续交换直到更新位置，以使新的根成为该元素。

现在，我们回到原来的delete_minimum()函数！我们可以简单地删除新的根目录！

这样，我们的整个删除过程将如下所示：

MinHeap* delete_element(MinHeap* heap, int index) {
  //Deletes an element, indexed by index
  //Ensure that it's lesser than the current root
  heap->arr[index] = get_min(heap) - 1;
  
  //Now keep swapping, until we update the tree
  int curr = index;
  while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
      int temp = heap->arr[parent(curr)];
      heap->arr[parent(curr)] = heap->arr[curr];
      heap->arr[curr] = temp;
      curr = parent(curr);
  }

  //Now simply delete the minimum element
  heap = delete_minimum(heap);
  return heap;
}

！我们终于完成了。
现在，我将向您展示整个代码以及" print()"函数，以可视化该树。

完整代码

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

typedef struct MinHeap MinHeap;
struct MinHeap {
  int* arr;
  //Current Size of the Heap
  int size;
  //Maximum capacity of the heap
  int capacity;
};

int parent(int i) {
  //Get the index of the parent
  return (i - 1)/2;
}

int left_child(int i) {
  return (2*i + 1);
}

int right_child(int i) {
  return (2*i + 2);
}

int get_min(MinHeap* heap) {
  //Return the root node element,
  //since that's the minimum
  return heap->arr[0];
}

MinHeap* init_minheap(int capacity) {
  MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
  minheap->arr = (int*) calloc (capacity, sizeof(int));
  minheap->capacity = capacity;
  minheap->size = 0;
  return minheap;
}

MinHeap* insert_minheap(MinHeap* heap, int element) {
  //Inserts an element to the min heap
  //We first add it to the bottom (last level)
  //of the tree, and keep swapping with it's parent
  //if it is lesser than it. We keep doing that until
  //we reach the root node. So, we will have inserted the
  //element in it's proper position to preserve the min heap property
  if (heap->size == heap->capacity) {
      fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
      return heap;
  }
  //We can add it. Increase the size and add it to the end
  heap->size++;
  heap->arr[heap->size - 1] = element;

  //Keep swapping until we reach the root
  int curr = heap->size - 1;
  //As long as you aren't in the root node, and while the 
  //parent of the last element is greater than it
  while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
      //Swap
      int temp = heap->arr[parent(curr)];
      heap->arr[parent(curr)] = heap->arr[curr];
      heap->arr[curr] = temp;
      //Update the current index of element
      curr = parent(curr);
  }
  return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
  //Rearranges the heap as to maintain
  //the min-heap property
  if (heap->size <= 1)
      return heap;
  
  int left = left_child(index); 
  int right = right_child(index); 

  //Variable to get the smallest element of the subtree
  //of an element an index
  int smallest = index; 
  
  //If the left child is smaller than this element, it is
  //the smallest
  if (left < heap->size && heap->arr[left] < heap->arr[index]) 
      smallest = left; 
  
  //Similarly for the right, but we are updating the smallest element
  //so that it will definitely give the least element of the subtree
  if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
      smallest = right; 

  //Now if the current element is not the smallest,
  //swap with the current element. The min heap property
  //is now satisfied for this subtree. We now need to
  //recursively keep doing this until we reach the root node,
  //the point at which there will be no change!
  if (smallest != index) 
  { 
      int temp = heap->arr[index];
      heap->arr[index] = heap->arr[smallest];
      heap->arr[smallest] = temp;
      heap = heapify(heap, smallest); 
  }

  return heap;
}

MinHeap* delete_minimum(MinHeap* heap) {
  //Deletes the minimum element, at the root
  if (!heap || heap->size == 0)
      return heap;

  int size = heap->size;
  int last_element = heap->arr[size-1];
  
  //Update root value with the last element
  heap->arr[0] = last_element;

  //Now remove the last element, by decreasing the size
  heap->size--;
  size--;

  //We need to call heapify(), to maintain the min-heap
  //property
  heap = heapify(heap, 0);
  return heap;
}

MinHeap* delete_element(MinHeap* heap, int index) {
  //Deletes an element, indexed by index
  //Ensure that it's lesser than the current root
  heap->arr[index] = get_min(heap) - 1;
  
  //Now keep swapping, until we update the tree
  int curr = index;
  while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
      int temp = heap->arr[parent(curr)];
      heap->arr[parent(curr)] = heap->arr[curr];
      heap->arr[curr] = temp;
      curr = parent(curr);
  }

  //Now simply delete the minimum element
  heap = delete_minimum(heap);
  return heap;
}

void print_heap(MinHeap* heap) {
  //Simply print the array. This is an
  //inorder traversal of the tree
  printf("Min Heap:\n");
  for (int i=0; i<heap->size; i++) {
      printf("%d -> ", heap->arr[i]);
  }
  printf("\n");
}

void free_minheap(MinHeap* heap) {
  if (!heap)
      return;
  free(heap->arr);
  free(heap);
}

int main() {
  //Capacity of 10 elements
  MinHeap* heap = init_minheap(10);

  insert_minheap(heap, 40);
  insert_minheap(heap, 50);
  insert_minheap(heap, 5);
  print_heap(heap);
  
  //Delete the heap->arr[1] (50)
  delete_element(heap, 1);

  print_heap(heap);
  free_minheap(heap);
  return 0;
}

输出

Min Heap:
5 -> 50 -> 40 -> 
Min Heap:
5 -> 40 -> 

实施的时间复杂度

上述过程的时间复杂度如下：