一、堆排序 Heap Sort
1. 前提条件

堆排序用的是：二叉堆

如果要升序排序：用大根堆

因为大根堆堆顶是最大值。

2. 核心思想

升序排序：

1. 先把数组建成大根堆
2. 堆顶就是最大值
3. 把堆顶和最后一个元素交换
4. 堆大小减 1
5. 对新的堆顶做下滤
6. 重复直到排序完成
3. 为什么用大根堆升序？

例如：

[4, 1, 7, 3]

建大根堆后：

堆顶 = 最大值 7

把 7 放到数组最后：

[?, ?, ?, 7]

然后继续找剩下元素最大值，放到倒数第二个。

所以最后就是升序。

4. 大根堆下滤代码
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void siftDownMax(int arr[], int size, int i)
{
    while(1)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if(left < size && arr[left] > arr[largest])
        {
            largest = left;
        }

        if(right < size && arr[right] > arr[largest])
        {
            largest = right;
        }

        if(largest == i)
        {
            break;
        }

        swap(&arr[i], &arr[largest]);

        i = largest;
    }
}

5. 建大根堆
void buildMaxHeap(int arr[], int size)
{
    for(int i = size / 2 - 1; i >= 0; i--)
    {
        siftDownMax(arr, size, i);
    }
}

为什么从：

size / 2 - 1

开始？

因为这是最后一个非叶子节点。

叶子节点没有孩子，天然满足堆性质。

6. 堆排序完整代码
void heapSort(int arr[], int size)
{
    buildMaxHeap(arr, size);

    for(int end = size - 1; end > 0; end--)
    {
        swap(&arr[0], &arr[end]);

        siftDownMax(arr, end, 0);
    }
}
7. 例子流程
arr = [4, 1, 7, 3]

建大根堆后，可能变成：

[7, 3, 4, 1]

交换堆顶和最后：

[1, 3, 4, 7]

现在 7 已经排好。

对前 3 个元素下滤：

[4, 3, 1, 7]

交换堆顶和下标 2：

[1, 3, 4, 7]

对前 2 个元素下滤：

[3, 1, 4, 7]

交换：

[1, 3, 4, 7]

排序完成。

8. 堆排序复杂度
建堆：O(n)

每次删除堆顶：O(log n)

总共删除 n 次：

O(n log n)

空间复杂度：

O(1)

因为直接在原数组上交换。

9. 易错点
升序排序用大根堆

降序排序用小根堆

堆排序不是稳定排序

siftDown 的 size 会不断变小

交换到末尾的元素已经排好，不再参与堆调整

二、优先队列 Priority Queue
1. 前提条件

普通队列：

先进先出 FIFO

优先队列：

优先级高的先出

例如：

医院急诊
任务调度
Dijkstra 最短路
Top K 问题
2. 核心概念

优先队列通常用堆实现。

小根堆：

每次弹出最小值

大根堆：

每次弹出最大值
3. 优先队列 ADT

常用操作：

init       初始化
push       插入元素
top        查看最高优先级元素
pop        删除最高优先级元素
isEmpty    判空
三、小根堆优先队列代码
1. 结构体
#include <stdlib.h>

struct PriorityQueue
{
    int* data;
    int size;
    int capacity;
};
2. 创建优先队列
struct PriorityQueue* createPriorityQueue(int capacity)
{
    struct PriorityQueue* pq =
        malloc(sizeof(struct PriorityQueue));

    pq->data = malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;

    return pq;
}
3. 判空
int isEmpty(struct PriorityQueue* pq)
{
    return pq->size == 0;
}
4. push：插入元素

小根堆，插入后上滤。

int push(struct PriorityQueue* pq, int x)
{
    if(pq->size == pq->capacity)
    {
        return 0;
    }

    int i = pq->size;
    pq->data[i] = x;
    pq->size++;

    while(i > 0)
    {
        int parent = (i - 1) / 2;

        if(pq->data[parent] <= pq->data[i])
        {
            break;
        }

        swap(&pq->data[parent], &pq->data[i]);

        i = parent;
    }

    return 1;
}
5. top：查看堆顶
int top(struct PriorityQueue* pq, int* x)
{
    if(isEmpty(pq))
    {
        return 0;
    }

    *x = pq->data[0];

    return 1;
}
6. pop：删除堆顶
int pop(struct PriorityQueue* pq, int* x)
{
    if(isEmpty(pq))
    {
        return 0;
    }

    *x = pq->data[0];

    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;

    int i = 0;

    while(1)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if(left < pq->size && pq->data[left] < pq->data[smallest])
        {
            smallest = left;
        }

        if(right < pq->size && pq->data[right] < pq->data[smallest])
        {
            smallest = right;
        }

        if(smallest == i)
        {
            break;
        }

        swap(&pq->data[i], &pq->data[smallest]);

        i = smallest;
    }

    return 1;
}
7. 释放
void destroyPriorityQueue(struct PriorityQueue* pq)
{
    free(pq->data);
    free(pq);
}
四、优先队列完整模板
#include <stdlib.h>

struct PriorityQueue
{
    int* data;
    int size;
    int capacity;
};

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

struct PriorityQueue* createPriorityQueue(int capacity)
{
    struct PriorityQueue* pq =
        malloc(sizeof(struct PriorityQueue));

    pq->data = malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;

    return pq;
}

int isEmpty(struct PriorityQueue* pq)
{
    return pq->size == 0;
}

int push(struct PriorityQueue* pq, int x)
{
    if(pq->size == pq->capacity)
    {
        return 0;
    }

    int i = pq->size;
    pq->data[i] = x;
    pq->size++;

    while(i > 0)
    {
        int parent = (i - 1) / 2;

        if(pq->data[parent] <= pq->data[i])
        {
            break;
        }

        swap(&pq->data[parent], &pq->data[i]);

        i = parent;
    }

    return 1;
}

int top(struct PriorityQueue* pq, int* x)
{
    if(isEmpty(pq))
    {
        return 0;
    }

    *x = pq->data[0];

    return 1;
}

int pop(struct PriorityQueue* pq, int* x)
{
    if(isEmpty(pq))
    {
        return 0;
    }

    *x = pq->data[0];

    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;

    int i = 0;

    while(1)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if(left < pq->size && pq->data[left] < pq->data[smallest])
        {
            smallest = left;
        }

        if(right < pq->size && pq->data[right] < pq->data[smallest])
        {
            smallest = right;
        }

        if(smallest == i)
        {
            break;
        }

        swap(&pq->data[i], &pq->data[smallest]);

        i = smallest;
    }

    return 1;
}

void destroyPriorityQueue(struct PriorityQueue* pq)
{
    free(pq->data);
    free(pq);
}

五、堆排序 vs 优先队列
堆排序：

目标是把整个数组排好序

核心操作：
    建堆
    反复把堆顶放到末尾

--------------------------------

优先队列：

目标是动态维护最大/最小值

核心操作：
    push
    top
    pop
六、最终笔记总结
堆排序：

升序：
    建大根堆

步骤：
    1. 建大根堆
    2. 堆顶和末尾交换
    3. 堆大小减一
    4. 对堆顶下滤
    5. 重复

复杂度：
    O(n log n)

空间：
    O(1)

--------------------------------

优先队列：

普通队列：
    先进先出

优先队列：
    优先级最高先出

实现：
    二叉堆

小根堆：
    top 是最小值

大根堆：
    top 是最大值

操作：
    push O(log n)
    pop O(log n)
    top O(1)

堆排序是“用堆把数组排好”；优先队列是“用堆动态维护当前最大或最小”。