C语言堆学习笔记

1. 堆的定义

堆（Heap）是一种特殊的树形数据结构，它满足以下性质：

堆是一个完全二叉树。
堆中每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。

1.1 最大堆

在最大堆中，父节点的值总是大于或等于子节点的值。

1.2 最小堆

在最小堆中，父节点的值总是小于或等于子节点的值。

2. 堆的表示方法

堆通常使用数组来表示，因为堆是完全二叉树，可以很方便地用数组存储。

2.1 数组表示法

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

3. 堆的基本操作

3.1 插入操作

插入新元素时，先将其放在堆的末尾，然后通过上滤（sift-up）操作将其移动到正确的位置。

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} Heap;

void initHeap(Heap* heap) {
    heap->size = 0;
}

void siftUp(Heap* heap, int index) {
    int parent = (index - 1) / 2;
    while (index > 0 && heap->data[parent] < heap->data[index]) {
        int temp = heap->data[parent];
        heap->data[parent] = heap->data[index];
        heap->data[index] = temp;
        index = parent;
        parent = (index - 1) / 2;
    }
}

void insert(Heap* heap, int value) {
    if (heap->size == MAX_SIZE) {
        printf("Heap overflow\n");
        return;
    }
    heap->data[heap->size] = value;
    siftUp(heap, heap->size);
    heap->size++;
}

3.2 删除操作

删除堆顶元素时，用堆的最后一个元素替换堆顶元素，然后通过下滤（sift-down）操作将其移动到正确的位置。

void siftDown(Heap* heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;
    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 != index) {
        int temp = heap->data[index];
        heap->data[index] = heap->data[largest];
        heap->data[largest] = temp;
        siftDown(heap, largest);
    }
}

int deleteMax(Heap* heap) {
    if (heap->size == 0) {
        printf("Heap underflow\n");
        return -1;
    }
    int max = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    siftDown(heap, 0);
    return max;
}

3.3 堆排序

堆排序（Heap Sort）是一种利用堆这种数据结构所设计的排序算法。

void heapify(Heap* heap) {
    for (int i = (heap->size / 2) - 1; i >= 0; i--) {
        siftDown(heap, i);
    }
}

void heapSort(int* array, int size) {
    Heap heap;
    initHeap(&heap);
    for (int i = 0; i < size; i++) {
        insert(&heap, array[i]);
    }
    heapify(&heap);
    for (int i = size - 1; i >= 0; i--) {
        array[i] = deleteMax(&heap);
    }
}

4. 堆的应用

4.1 优先队列

堆实现的优先队列可以在O(log n)时间内插入元素和删除最大（或最小）元素。

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

typedef struct {
    Heap heap;
} PriorityQueue;

void initPriorityQueue(PriorityQueue* pq) {
    initHeap(&pq->heap);
}

void enqueue(PriorityQueue* pq, int value) {
    insert(&pq->heap, value);
}

int dequeue(PriorityQueue* pq) {
    return deleteMax(&pq->heap);
}

4.2 堆排序

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

void heapSort(int* array, int size) {
    Heap heap;
    initHeap(&heap);
    for (int i = 0; i < size; i++) {
        insert(&heap, array[i]);
    }
    heapify(&heap);
    for (int i = size - 1; i >= 0; i--) {
        array[i] = deleteMax(&heap);
    }
}