堆排序等操作

一、堆排序 Heap Sort

1. 前提条件

堆排序用的是：二叉堆

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

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

2. 核心思想

升序排序：

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

例如：

[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)

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