堆的基本操作

引言

堆是一种特殊的完全二叉树结构，常用于实现优先队列。在最大堆中，父节点的值总是大于或等于其子节点的值。本文将通过C语言代码实现一个最大堆

堆的基本概念

堆是一种数据结构，具有以下特性：

• 完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点都靠左排列
• 堆序性：在最大堆中，任意节点的值大于或等于其子节点的值

堆通常用数组来实现，其中：

• 根节点索引: 0
• 左子节点索引：2*i + 1
• 右子节点索引：2*i + 2
• 父节点索引： (i-1)/2

代码实现

下面是最大堆的C语言实现

1. 堆的结构体定义

typedef struct {
    int *data;      // 动态数组，数组指针
    int size;       // 堆的元素个数
    int capacity;   // 堆的最大容量
} MaxHeap;

2. 交换元素

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

3. 初始化堆

MaxHeap* createHeap(int capacity) {
    // 初始化分配空间
    MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
    heap->data = (int*)malloc(sizeof(int) * capacity);
    // 堆数值初始化
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}

4. 向上调整（siftUp）

用于插入元素后维护堆的性质。从插入的节点开始，与父节点比较，如果大于父节点则交换，直到满足堆序性

void siftUp(MaxHeap* heap, int childIdx) {
    while (childIdx > 0) {
        int parentIdx = (childIdx - 1) / 2;
        if (heap->data[childIdx] > heap->data[parentIdx]) {
            swap(&heap->data[childIdx], &heap->data[parentIdx]);
            childIdx = parentIdx;
        } else {
            break;
        }
    }
}

5. 向下调整（siftDown）

用于删除堆顶或建堆时维护堆的性质。从指定节点开始，与子节点比较，选择最大的子节点交换，直到满足堆序性

void siftDown(MaxHeap* heap, int parentIdx) {
    int size = heap->size;
    while (true) {
        int leftChild = parentIdx * 2 + 1;
        int rightChild = parentIdx * 2 + 2;
        int largest = parentIdx;
        
        if (leftChild < size && heap->data[leftChild] > heap->data[largest]) {
            largest = leftChild;
        }
        if (rightChild < size && heap->data[rightChild] > heap->data[largest]) {
            largest = rightChild;
        }
        if (largest != parentIdx) {
            swap(&heap->data[largest], &heap->data[parentIdx]);
            parentIdx = largest;
        } else {
            break;
        }
    }
}

6. 入堆操作（push）

bool push(MaxHeap* heap, int val) {
    // 满堆的处理
    if (heap->size == heap->capacity)
        return false;

    heap->data[heap->size] = val;

    // 这里siftUp与size无关，所以两者顺序不影响
    siftUp(heap, heap->size);
    heap->size++;
    return true;
}

7. 出堆操作（pop）

int pop(MaxHeap* heap) {
    // 空堆检查
    if (heap->size == 0) return -1;
    int root = heap->data[0];     
    
    // 用最后一个元素覆盖堆顶
    heap->data[0] = heap->data[heap->size - 1];
    
    // 必须先减size再siftDown：
    // 1. siftDown依赖正确的heap->size判断子节点边界
    // 2. 原末尾元素已移至堆顶，该位置不再属于堆
    // 3. 避免siftDown访问到逻辑上已移除的元素
    heap->size--;  
    siftDown(heap, 0);
    return root;
}

8. 删除任意位置的元素

void deleteElement(MaxHeap* heap, int i) {
    if (i < 0 || i >= heap->size)
        return;
    if (i == 0) {
        pop(heap);
        return;
    }
    if (i == heap->size - 1) {
        heap->size--;
        return;
    }
    int lastVal = heap->data[heap->size - 1];
    heap->size--;
    int oldVal = heap->data[i];
    heap->data[i] = lastVal;

    if (lastVal > oldVal) {
        siftUp(heap, i);
    } else {
        siftDown(heap, i);
    }
}

9. 建堆操作

MaxHeap* makeHeap(int* nums, int numsSize) {
    // 堆的初始化
    MaxHeap* heap = createHeap(numsSize);
    // 数组拷贝到堆
    memcpy(heap->data, nums, numsSize * sizeof(int));
    heap->size = numsSize;
    // 从最后一个非叶节点开始向下调整
    for (int i = (numsSize / 2) - 1; i >= 0; i--) {
        siftDown(heap, i);
    }
    return heap;
}

总结

通过以上代码，我们实现了一个完整的大根堆数据结构，堆的基本操作包括：

• 插入：使用push函数，时间复杂度O(log n)
• 删除堆顶：使用pop函数，时间复杂度O(log n)
• 删除任意元素：使用deleteElement函数，时间复杂度O(log n)
• 建堆：使用makeHeap函数，时间复杂度O(n)