最小堆二叉树数据结构详解：原理、实现与应用

这是文章《最小堆二叉树》的第1部分（共9部分）。

一个最小堆二叉树是一棵二叉树，其中根节点的关键字是树中的最小值。

上述定义对树中的所有子树都适用，这被称为最小堆属性。

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

以下树是一个最小堆二叉树的示例，因为上述两个属性成立。

既然我们已经讲解了什么是最小堆二叉树，那么现在让我们看看如何表示它。

---

最小堆二叉树的表示

一个最小堆二叉树通常用数组表示，数组的索引按以下格式排序。

整个树的根节点是 arr[0]。

我们将使用下图所示的索引。在这里找到匹配上表的模式并不太困难。

这种索引方式遵循二叉树的层序遍历，因此二叉堆数组是使用层序遍历的二叉树。

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

现在我们已经了解了这些概念，让我们开始在C语言中实现吧！

---

实现一个最小堆二叉树

这是文章《最小堆二叉树》的第2部分（共9部分）。

我们将使用数组表示来构建树。让我们开始编写最小堆的结构。

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // 堆的当前大小
    int size;
    // 堆的最大容量
    int capacity;
};

我们会有一个元素数组和一个大小，大小会在插入或删除元素时进行更新。

数组还有一个容量，用来表示数组的最大尺寸。

我们需要写几个函数来表示我们正在表示一个最小堆，比如找到父节点和子节点。

int parent(int i) {
    // 获取父节点的索引
    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 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);
}

好的，既然这个问题解决了，现在让我们来讨论如何插入元素吧！

插入到小顶堆中

这是文章《最小堆二叉树》的第3部分（共9部分）。

内容片段: 插入算法很简单。它将一个元素插入到树中。

分解算法:

• 首先，总是在树的底部插入。插入元素的初始位置位于最后一层。
• 现在我们需要更新这个元素的位置，以满足最小堆的性质。
• 由于每个子树的根节点必须是最小值，因此检查其直接父节点的子树。
• 如果父节点大于这个插入的元素，我们需要通过交换来更新它的位置。
• 但我们还没有完成，因为更新节点的子树可能违反最小堆的性质！
• 我们需要继续交换，直到到达根节点，之后我们就完成了。

为了理解这个过程，让我们举个例子来说明。

考虑下方仅含有一个元素的树。

让我们插入元素40。由于只有一个元素，它被插入到底部，并且我们观察到最小堆属性得到满足，因为10 < 40。所以不需要进行交换。

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

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

子树1-3违反了最小堆的属性，因此整个树也会受到影响。因此，我们必须不断与父节点交换，直到达到根节点为止。

所以，我们还需要进行一次交换，因为在以节点0为根的子树中，最小堆的属性再次被违反了。

好的，既然我们已经可视化了，那就把它写下来吧！

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // 向最小堆中插入一个元素
    // 我们首先将元素添加到树的底部（最后一层）
    // 如果它比其父节点小，则不断与父节点交换
    // 我们持续这个过程直到到达根节点
    // 这样，我们就将元素插入到了适当的位置，以保持最小堆的性质
    if (heap->size == heap->capacity) {
        fprintf(stderr, "无法插入 %d。堆已满！\n", element);
        return heap;
    }
    // 可以添加元素。增加堆的大小并将元素添加到末尾
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // 持续交换直到到达根节点
    int curr = heap->size - 1;
    // 只要不在根节点，并且最后一个元素的父节点大于它
    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);
    }
    return heap; 
}

我们现在要实施删除方法。

从最小堆中删除

在探讨如何删除任意索引位置的元素之前，由于最小堆的特性与根节点密切相关，我们将首先研究删除根节点的情况。

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

• 将根节点更新为数组（树）的最后一个元素
• 现在我们将移除底部的最后一个元素。这类似于在末尾进行交换和删除！只是因为我们不再关心根节点的值，所以直接更新它即可。
• 问题在于我们需要维护最小堆的性质。
• 因此，我们必须确保整个树都保持这一性质。我们将使用一个名为heapify()的函数来完成这个任务。

因此，我们知道在执行heapify()方法之后，删除操作就完成了。

MinHeap* delete_minimum(MinHeap* heap) {
    // 删除根节点的最小元素
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // 用最后一个元素更新根节点值
    heap->arr[0] = last_element;

    // 通过减小堆的大小来移除最后一个元素
    heap->size--;
    size--;

    // 我们需要调用heapify()来维护最小堆
    // 的性质
    heap = heapify(heap, 0);
    return heap;
}

堆化（heapify()）的过程

这个函数接受一个元素的索引index，并通过与其直接子树中最小的元素交换来保持最小堆的性质。

生成的树将满足最小堆性质。

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

在这之后，我们还需要确保整个树满足这一条件。所以，我们需要递归地在最小元素上调用这个过程，直到达到根节点为止！

MinHeap* heapify(MinHeap* heap, int index) {
    // 重新排列堆以维护
    // 最小堆性质
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // 用于获取子树中最小元素的变量
    // 在给定索引位置的元素
    int smallest = index; 
    
    // 如果左子节点小于当前元素，则
    // 它是最小的
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // 类似地处理右子节点，但我们更新最小元素
    // 以确保一定能得到子树中的最小元素
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // 现在，如果当前元素不是最小的，
    // 与当前元素交换。最小堆性质
    // 现在对于这个子树已经满足。我们现在需要
    // 递归地继续执行此操作，直到到达根节点，
    // 那时将不再有任何变化！
    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()函数，来删除任何元素。

删除一个任意元素

这是文章《最小堆二叉树》的第7部分（共9部分）。

这一步骤仅涉及将目标元素设置为最小可能值，即get_min()-1，因为它必须小于当前最小值。

接下来，我们将继续进行交换操作，直到更新元素位置，使该元素成为新的根节点。

现在，我们可以使用之前定义的delete_minimum()函数！这样我们就能简单地删除新的根节点！

基于以上步骤，我们完整的元素删除过程将如下所示：

MinHeap* delete_element(MinHeap* heap, int index) {
    // 删除指定索引位置的元素
    // 确保该值小于当前根节点的值
    heap->arr[index] = get_min(heap) - 1;
    
    // 持续交换，直到更新整个树结构
    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);
    }

    // 现在只需删除最小元素
    heap = delete_minimum(heap);
    return heap;
}

太好了！我们终于完成了最小堆中删除任意元素的实现。接下来，我将展示完整的代码，包括用于可视化树结构的print()函数。

---

完整的代码实现

最小堆二叉树的C语言实现

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

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // 堆的当前大小
    int size;
    // 堆的最大容量
    int capacity;
};

int parent(int i) {
    // 获取父节点的索引
    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 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) {
    // 向最小堆插入元素
    // 我们首先将其添加到树的底部（最后一层），
    // 如果它比父节点小，则不断与父节点交换。
    // 我们一直这样做，直到到达根节点。
    // 这样，我们就将元素插入到了正确的位置，以保持最小堆的性质
    if (heap->size == heap->capacity) {
        fprintf(stderr, "无法插入 %d。堆已满！\n", element);
        return heap;
    }
    // 可以添加。增加大小并将其添加到末尾
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // 持续交换直到到达根节点
    int curr = heap->size - 1;
    // 只要不在根节点，并且最后一个元素的父节点大于它
    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);
    }
    return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
    // 重新排列堆以保持最小堆性质
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // 用于获取索引处元素子树中最小元素的变量
    int smallest = index; 
    
    // 如果左子节点小于此元素，则它是最小的
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // 右子节点同理，但我们正在更新最小元素，
    // 以便它一定能给出子树中的最小元素
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // 现在，如果当前元素不是最小的，则与当前元素交换。
    // 现在，此子树的最小堆性质得到满足。
    // 我们现在需要递归地继续这样做，直到到达根节点，
    // 此时将不再有变化！
    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) {
    // 删除根节点的最小元素
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // 用最后一个元素更新根值
    heap->arr[0] = last_element;

    // 现在通过减小大小来移除最后一个元素
    heap->size--;
    size--;

    // 我们需要调用heapify()来保持最小堆性质
    heap = heapify(heap, 0);
    return heap;
}

MinHeap* delete_element(MinHeap* heap, int index) {
    // 删除索引处的元素
    // 确保它小于当前根节点
    heap->arr[index] = get_min(heap) - 1;
    
    // 现在持续交换，直到我们更新树
    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);
    }

    // 现在只需删除最小元素
    heap = delete_minimum(heap);
    return heap;
}

void print_heap(MinHeap* heap) {
    // 简单地打印数组。这是树的中序遍历
    printf("最小堆：\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() {
    // 容量为10个元素
    MinHeap* heap = init_minheap(10);

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

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

输出结果

最小堆：
5 -> 50 -> 40 -> 
最小堆：
5 -> 40 -> 

---

实现的时间复杂度

最小堆的各个操作具有不同的时间复杂度，了解这些复杂度对于评估算法效率至关重要：

• 初始化堆（init_minheap）：O(1) – 仅分配内存并设置初始值
• 获取最小值（get_min）：O(1) – 直接返回根节点元素
• 插入元素（insert_minheap）：O(log n) – 最坏情况下需要从叶子节点到根节点进行交换
• 删除最小值（delete_minimum）：O(log n) – 删除根节点后需要重新调整堆结构
• 删除指定元素（delete_element）：O(log n) – 需要先调整元素位置，再删除最小值
• 堆化（heapify）：O(log n) – 从指定节点向下调整堆结构

最小堆的时间复杂度优势主要体现在频繁获取最小值和动态维护数据集的场景中。相比线性搜索最小值的O(n)复杂度，最小堆的O(1)获取最小值和O(log n)的插入删除操作使其在优先队列、图算法（如Dijkstra算法）和堆排序等应用中表现出色。

---

下载代码

你可以从我上传的Github Gist中下载完整的代码。如果对此有任何疑问，请在下面的评论区询问！

---

结论

在这篇文章中，我们学习了如何表示最小堆二叉树，并且还看了一种在C语言中的实现方式。

参考文献

• 堆的图解，来自Cormen
• 关于二叉堆的维基百科文章