堆（Heap）的实现：基于完全二叉树的顺序存储与调整算法

删除堆顶 / 堆排序。

核心思想

每次选'更大的孩子'，和父节点比较。

标准代码（推荐写法）

void AdjustDown(int* a, int n, int parent) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child]) {
            child++;
        }
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

设计巧妙点

1. 用左孩子控制循环（覆盖所有情况）
2. 用右孩子判断做分支（避免越界）
3. 把'左右比较'压缩成'选最优孩子'

三种情况全覆盖

五、关键易错点总结

1. 顺序写反导致越界

   • ❌ a[child + 1] > a[child] && child + 1 < n
   • ✅ child + 1 < n && a[child + 1] > a[child]
   • 👉 利用短路避免越界

2. 忘记 break

   • 👉 会死循环

3. 用右孩子做循环条件

   • ❌ while (child + 1 < n)
   • 👉 会漏掉'只有左孩子'的情况

六、堆的核心接口实现

插入

void HPPush(HP* php, int x) {
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        int* tmp = (int*)realloc(php->a, sizeof(int) * newcapacity);
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

删除

void HPPop(HP* php) {
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

七、内存管理（非常重要）

原则

谁 malloc，谁 free。

易错点

• free(php); ❌（如果是栈变量）

推荐写法

void HPDestroy(HP* php) {
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

八、常见问题总结

1. 为什么 AdjustDown 要传 n？

   • n 用来限制'堆的有效范围'，防止访问已被移除的元素。

2. 为什么用左孩子做循环条件？

   • 因为：有右孩子 ⇒ 一定有左孩子。左孩子能覆盖所有情况。

3. 为什么不会越界？

   • 因为：child + 1 < n && ...，利用短路机制避免访问非法内存。

4. 三目运算符怎么用？

   • child = (child + 1 < n && a[child + 1] > a[child]) ? child + 1 : child;

5. parent 为什么写在外面？

   • 初始化 + 循环更新，结构更清晰。

九、进阶理解（非常关键）

本质

堆的调整不是'改整棵树'，而是修复一条路径。

时间复杂度

• O(log n)

十、拓展 & 面试考点

1. 堆排序（必考）

for (int i = n - 1; i > 0; i--) {
    Swap(&a[0], &a[i]);
    AdjustDown(a, i, 0);
}

2. TopK 问题

   • 👉 用小堆维护前 K 大元素

3. 优先级队列

   • 👉 堆的直接应用

4. 建堆（Heapify）

for (int i = (n - 2) / 2; i >= 0; i--) {
    AdjustDown(a, n, i);
}

面试高频问法

• 为什么从 (n-2)/2 开始？
• AdjustUp 和 AdjustDown 区别？
• 堆和二叉搜索树区别？
• 堆排序稳定吗？（❌ 不稳定）

最终总结

• 堆 = 数组 + 完全二叉树映射
• 核心：插入 → 向上调整；删除 → 向下调整
• 本质：局部破坏 → 路径修复

头文件 (Heap.h)

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HPDateType;

typedef struct Heap {
    HPDateType* a;
    int size;
    int capacity;
} HP;

void Swap(HPDateType* p1, HPDateType* p2);
void AdjustUp(HPDateType* a, int child);
void AdjustDown(HPDateType* a, int n, int parent);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDateType x);
void HPPop(HP* php);
HPDateType HPTop(HP* php);
bool HPEmpty(HP* php);
void CreatHeap(int* a, int n);
void HeapSort(int* a, int n);

源文件 (Heap.c)

#include "Heap.h"

void Swap(HPDateType* p1, HPDateType* p2) {
    assert(p1 && p2);
    HPDateType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustUp(HPDateType* a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

void AdjustDown(HPDateType* a, int n, int parent) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++;
        }
        if (a[parent] < a[child]) {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HPInit(HP* php) {
    php->a = NULL;
    php->capacity = php->size = 0;
}

void HPDestroy(HP* php) {
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

void HPPush(HP* php, HPDateType x) {
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : (php->capacity) * 2;
        HPDateType* temp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * newcapacity);
        if (temp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        php->a = temp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

void HPPop(HP* php) {
    assert(php);
    assert(php->size != 0);
    Swap(&(php->a[php->size - 1]), &php->a[0]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

HPDateType HPTop(HP* php) {
    assert(php);
    assert(php->size != 0);
    return php->a[0];
}

bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

void CreatHeap(int* a, int n) {
    int i = (n - 2) / 2;
    for (; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
}

void HeapSort(int* a, int n) {
    int i = (n - 2) / 2;
    for (; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    int end = n - 1;
    while (end) {
        int tmp = a[0];
        a[0] = a[end];
        a[end] = tmp;
        AdjustDown(a, end, 0);
        end--;
    }
}