跳到主要内容

C 语言堆实现

介绍​

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆可以分为最大堆和最小堆两种类型。在最大堆中，每个父节点的值都大于或等于其子节点的值；而在最小堆中，每个父节点的值都小于或等于其子节点的值。

堆的一个重要特性是，堆的根节点总是包含最大或最小的元素，这使得堆在需要快速访问最大或最小元素的场景中非常有用。

堆的基本操作​

堆的基本操作包括：

  • 插入（Insert）：将一个新元素插入堆中，并保持堆的性质。
  • 删除（Delete）：删除堆中的根节点，并保持堆的性质。
  • 堆化（Heapify）：将一个数组转换为堆。

堆的表示​

在C语言中，堆通常使用数组来表示。对于一个索引为 i 的节点：

  • 其父节点的索引为 (i - 1) / 2
  • 其左子节点的索引为 2 * i + 1
  • 其右子节点的索引为 2 * i + 2

堆的实现​

1. 插入操作​

插入操作的基本步骤如下：

  1. 将新元素插入到数组的末尾。
  2. 从新插入的节点开始，向上调整堆，直到满足堆的性质。
c
void insert(int heap[], int *size, int value) {
    if (*size == MAX_HEAP_SIZE) {
        printf("Heap is full!\n");
        return;
    }
    heap[*size] = value;
    int i = *size;
    (*size)++;
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        int temp = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

2. 删除操作​

删除操作的基本步骤如下：

  1. 将堆的根节点与最后一个节点交换。
  2. 删除最后一个节点。
  3. 从根节点开始，向下调整堆，直到满足堆的性质。
c
void delete(int heap[], int *size) {
    if (*size == 0) {
        printf("Heap is empty!\n");
        return;
    }
    heap[0] = heap[*size - 1];
    (*size)--;
    int i = 0;
    while (i < *size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < *size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < *size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            i = largest;
        } else {
            break;
        }
    }
}

3. 堆化操作​

堆化操作是将一个数组转换为堆的过程。通常从最后一个非叶子节点开始，向前遍历每个节点，并对其进行向下调整。

c
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

实际应用场景​

堆在实际应用中有很多用途，例如：

  • 优先队列：堆可以用来实现优先队列，确保每次都能快速访问到优先级最高的元素。
  • 堆排序：堆排序是一种高效的排序算法，利用堆的性质进行排序。
  • Dijkstra算法：在图的单源最短路径算法中，堆可以用来优化优先队列的操作。

总结​

堆是一种非常重要的数据结构，特别适合用于需要快速访问最大或最小元素的场景。通过本文的学习，你应该已经掌握了如何在C语言中实现堆的基本操作，包括插入、删除和堆化。希望你能通过实际编程练习进一步巩固这些知识。

附加资源与练习​

  • 练习1：实现一个最小堆，并测试其插入和删除操作。
  • 练习2：使用堆实现一个优先队列，并测试其功能。
  • 练习3：实现堆排序算法，并对一个随机数组进行排序。
提示

如果你对堆的实现还有疑问，可以参考《算法导论》中的相关章节，或者查阅更多关于堆的在线资源。