C语言实现堆的简单操作的示例代码

C语言实现堆的简单操作的示例代码

堆的定义

堆是指通过比较之后使得数组满足大/小根堆性质的一种近似完全二叉树结构。

堆的结构

堆有两种类型，分别为大根堆和小根堆。大根堆指所有父结点都大于等于其子结点，小根堆则相反，所有父结点都小于等于其子结点。

假设i为当前结点，那么其父结点为(i-1)/2，左子结点为(2i+1)，右子结点为(2i+2)。

堆支持如下操作：

1. 将一个元素加入到堆中

2. 返回堆中最小/大值

3. 删除堆中最小/大值

堆的实现

要实现一个堆，需要用到下面几个重要的函数：

• MaxHeapify：将堆的某一个非叶子结点与子结点进行比较，从而得到大根堆。而对于小根堆，则是将其变为小根堆。

• BuildMaxHeap：建立堆，从无序的数组开始建立一个大根堆/小根堆

• HeapSort：对无序数组进行排序，由于最大/小值在根结点中，先将根结点（最大/小值）与最后一位进行交换，然后将除最后一位的剩余数组调整为大根堆

• Insert：插入一个元素，插到堆的尾部，调用_sift_up_ 负责新元素的上移操作

• DeleteMax：移除最大元素。将堆顶元素及末尾元素交换，移除末尾元素，再调用_sift_down_ 负责新顶点的下移操作。

• Heapify：将任一数组变成堆。

下面我们通过代码实现堆的基本操作：插入和删除最大值

插入操作

void insert(int arr[], int n, int value){
    arr[n] = value;  // 新元素插在末尾
    int i = n;
    while(i > 0 && arr[(i-1)/2] < arr[i]){  // 如果新元素比父结点大，与父结点交换
        swap(arr[i], arr[(i-1)/2]);
        i = (i-1)/2;
    }
}

在这个函数中，首先将新元素插在末尾，然后使用while循环，循环条件保证了当前结点的父结点存在且其值小于当前结点的值，最后交换两者。这样的操作被称为_sift-up_，因为新元素已经插入到堆中，我们需要将其“上移”以保证堆的性质。

删除最大值

int remove(int arr[], int n){
    // 先将堆顶和堆底交换
    int root_value = arr[0];
    arr[0] = arr[n-1];
    n--;
    // 然后对堆顶执行_sift-down_
    int i = 0;
    while(i < n){
        int max_value = arr[i];
        int max_index = i;
        // 发现左子结点比当前结点大
        if(2*i + 1 < n && arr[2*i + 1] > max_value){
            max_value = arr[2*i + 1];
            max_index = 2*i + 1;
        }
        // 发现右子结点比当前结点大
        if(2*i + 2 < n && arr[2*i + 2] > max_value){
            max_value = arr[2*i + 2];
            max_index = 2*i + 2;
        }
        // 堆的性质被满足，处理结束
        if(max_index == i){
            break;
        }
        swap(arr[max_index], arr[i]);
        i = max_index;
    }
    return root_value;
}

这个函数首先将堆顶（即最大值）与堆底（最右边值）进行交换。接着执行_sift-down_ 操作，将新的根结点下放到其应被放置的位置使得堆的性质被满足。这里需要不断地获取左右结点，并交换以满足堆的性质。这种方式被称为“sift-down”。

示例说明

以大根堆为例，给出以下无序数组：

int arr[] = {10, 20, 15, 40, 50, 30};
int n = sizeof(arr)/sizeof(arr[0]);

我们来分别看看其插入和删除最大值之后的操作：

插入操作

如果在这个堆中插入元素60：

insert(arr, n, 60);

那么堆就变成：

60, 20, 15, 10, 50, 30, 40

删除最大值操作

如果我们先执行一次insert(arr, n, 60)函数，然后再删除其中元素60：

int root_value = remove(arr, n);

那么堆就变成：

50, 20, 15, 10, 40, 30

最大值被返回并从本堆中删除。

总结

通过上述示例，我们可以清楚地看到添加和删除堆元素的操作及其具体实现。同时，我们还可以使用大根堆和小根堆对数组进行排序，以提高算法效率。可以看出，堆是一种相对简单而强大的数据结构。