如何用C语言实现堆结构

创作时间:

作者:

@小白创作中心

如何用C语言实现堆结构

引用

来源

https://docs.pingcode.com/baike/1520359

堆结构是一种重要的数据结构，广泛应用于优先队列、堆排序以及图算法等领域。本文将详细介绍如何使用C语言实现堆结构，包括堆的基本概念、数组表示法、插入操作、删除操作、堆化操作以及应用场景。

如何用C语言实现堆结构：使用数组实现、支持插入操作、支持删除操作、支持堆化操作。堆是一种特殊的完全二叉树，常用于实现优先队列。C语言通过数组实现堆结构，主要操作包括插入、删除和堆化。接下来，我们将详细探讨如何在C语言中实现这些操作。

一、堆的基本概念

1. 什么是堆

堆是一种特殊的完全二叉树，可以是最大堆（父节点的值总是大于或等于子节点的值）或最小堆（父节点的值总是小于或等于子节点的值）。堆通常用于优先队列的实现。

2. 数组表示法

堆通常用数组表示。对于一个节点i，其左子节点为2i+1，右子节点为2i+2，父节点为floor((i-1)/2)。

二、堆的操作

1. 插入操作

插入操作将新元素添加到堆的末尾，然后进行“上浮”操作，以保持堆的性质。

#include <stdio.h>
#include <stdlib.h>  
#define MAX_HEAP_SIZE 100  
typedef struct {  
    int size;  
    int data[MAX_HEAP_SIZE];  
} MaxHeap;  
void swap(int *a, int *b) {  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  
void insert(MaxHeap *heap, int value) {  
    if (heap->size >= MAX_HEAP_SIZE) {  
        printf("Heap is full!\n");  
        return;  
    }  
    heap->data[heap->size] = value;  
    int i = heap->size;  
    heap->size++;  
    while (i != 0 && heap->data[(i - 1) / 2] < heap->data[i]) {  
        swap(&heap->data[(i - 1) / 2], &heap->data[i]);  
        i = (i - 1) / 2;  
    }  
}

2. 删除操作

删除操作通常是删除堆顶元素，然后将最后一个元素移到堆顶，再进行“下沉”操作以保持堆的性质。

int extractMax(MaxHeap *heap) {
    if (heap->size <= 0) {  
        printf("Heap is empty!\n");  
        return -1;  
    }  
    if (heap->size == 1) {  
        heap->size--;  
        return heap->data[0];  
    }  
    int root = heap->data[0];  
    heap->data[0] = heap->data[heap->size - 1];  
    heap->size--;  
    int i = 0;  
    while (2 * i + 1 < heap->size) {  
        int largest = i;  
        if (heap->data[2 * i + 1] > heap->data[largest]) {  
            largest = 2 * i + 1;  
        }  
        if (2 * i + 2 < heap->size && heap->data[2 * i + 2] > heap->data[largest]) {  
            largest = 2 * i + 2;  
        }  
        if (largest == i) {  
            break;  
        }  
        swap(&heap->data[i], &heap->data[largest]);  
        i = largest;  
    }  
    return root;  
}

3. 堆化操作

堆化操作是将一个无序数组转换为堆结构，通常用于构建堆或修复堆的性质。

void heapify(MaxHeap *heap, int i) {
    int largest = i;  
    int left = 2 * i + 1;  
    int right = 2 * i + 2;  
    if (left < heap->size && heap->data[left] > heap->data[largest]) {  
        largest = left;  
    }  
    if (right < heap->size && heap->data[right] > heap->data[largest]) {  
        largest = right;  
    }  
    if (largest != i) {  
        swap(&heap->data[i], &heap->data[largest]);  
        heapify(heap, largest);  
    }  
}  
void buildHeap(MaxHeap *heap) {  
    for (int i = heap->size / 2 - 1; i >= 0; i--) {  
        heapify(heap, i);  
    }  
}

三、应用场景

1. 优先队列

堆结构是优先队列的基础，能够高效地支持插入和删除操作。

2. 堆排序

堆排序是一种基于堆的数据结构的排序算法，具有O(n log n)的时间复杂度。

void heapSort(int arr[], int n) {
    MaxHeap heap;  
    heap.size = n;  
    for (int i = 0; i < n; i++) {  
        heap.data[i] = arr[i];  
    }  
    buildHeap(&heap);  
    for (int i = n - 1; i >= 0; i--) {  
        arr[i] = extractMax(&heap);  
    }  
}

3. 图算法

在图算法中，堆用于实现Dijkstra算法和Prim算法，以提高效率。

四、代码示例

1. 完整代码

下面是一个完整的C语言实现堆结构的示例代码：

#include <stdio.h>
#include <stdlib.h>  
#define MAX_HEAP_SIZE 100  
typedef struct {  
    int size;  
    int data[MAX_HEAP_SIZE];  
} MaxHeap;  
void swap(int *a, int *b) {  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  
void insert(MaxHeap *heap, int value) {  
    if (heap->size >= MAX_HEAP_SIZE) {  
        printf("Heap is full!\n");  
        return;  
    }  
    heap->data[heap->size] = value;  
    int i = heap->size;  
    heap->size++;  
    while (i != 0 && heap->data[(i - 1) / 2] < heap->data[i]) {  
        swap(&heap->data[(i - 1) / 2], &heap->data[i]);  
        i = (i - 1) / 2;  
    }  
}  
int extractMax(MaxHeap *heap) {  
    if (heap->size <= 0) {  
        printf("Heap is empty!\n");  
        return -1;  
    }  
    if (heap->size == 1) {  
        heap->size--;  
        return heap->data[0];  
    }  
    int root = heap->data[0];  
    heap->data[0] = heap->data[heap->size - 1];  
    heap->size--;  
    int i = 0;  
    while (2 * i + 1 < heap->size) {  
        int largest = i;  
        if (heap->data[2 * i + 1] > heap->data[largest]) {  
            largest = 2 * i + 1;  
        }  
        if (2 * i + 2 < heap->size && heap->data[2 * i + 2] > heap->data[largest]) {  
            largest = 2 * i + 2;  
        }  
        if (largest == i) {  
            break;  
        }  
        swap(&heap->data[i], &heap->data[largest]);  
        i = largest;  
    }  
    return root;  
}  
void heapify(MaxHeap *heap, int i) {  
    int largest = i;  
    int left = 2 * i + 1;  
    int right = 2 * i + 2;  
    if (left < heap->size && heap->data[left] > heap->data[largest]) {  
        largest = left;  
    }  
    if (right < heap->size && heap->data[right] > heap->data[largest]) {  
        largest = right;  
    }  
    if (largest != i) {  
        swap(&heap->data[i], &heap->data[largest]);  
        heapify(heap, largest);  
    }  
}  
void buildHeap(MaxHeap *heap) {  
    for (int i = heap->size / 2 - 1; i >= 0; i--) {  
        heapify(heap, i);  
    }  
}  
void heapSort(int arr[], int n) {  
    MaxHeap heap;  
    heap.size = n;  
    for (int i = 0; i < n; i++) {  
        heap.data[i] = arr[i];  
    }  
    buildHeap(&heap);  
    for (int i = n - 1; i >= 0; i--) {  
        arr[i] = extractMax(&heap);  
    }  
}  
int main() {  
    MaxHeap heap;  
    heap.size = 0;  
    insert(&heap, 10);  
    insert(&heap, 20);  
    insert(&heap, 5);  
    insert(&heap, 30);  
    printf("Max element: %d\n", extractMax(&heap));  
    int arr[] = {10, 20, 15, 30, 40};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    heapSort(arr, n);  
    printf("Sorted array: ");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("\n");  
    return 0;  
}