二叉堆优先队列

依次入队：任务 A=40，B=10，C=30（数字越小越优先）
堆顶：B=10
第一次出队：B
新的堆顶：C=30
第二次出队：C
最后：A=40

private readonly List<MessageConfig> _heap = new();

_heap = [90, 70, 80, 30, 50, 60]

_heap = [90, 70, 85, 30, 50, 60, 80]

入队顺序: A(10), B(100), C(30)
出队顺序: A, B, C

插入 A(10) -> [10]
插入 B(100) -> [100, 10]
插入 C(30) -> [100, 30, 10]

[90, 70, 85, 30, 50, 60, 80]

生产者 → 等待区 → 调度器 → 活动区 → 到期回对象池

public MessageConfig Peek()
{
    return _heap.Count == 0 ? null : _heap[0];
}

我最频繁的问题是什么？
我愿意把成本花在插入、删除、查询的哪一步？

分类：数据结构

先说结论

优先队列保证每次取出当前优先级最高或最低的元素，但不保证所有元素整体有序。二叉堆通过一个局部不变量做到这一点：父节点始终不比子节点更差。

三个优先级怎样变化

依次入队：任务 A=40，B=10，C=30（数字越小越优先）
堆顶：B=10
第一次出队：B
新的堆顶：C=30
第二次出队：C
最后：A=40

堆内部数组可能是 [10, 40, 30]，这不是完整排序，但根节点已经足够回答“下一项是谁”。因此入队和出队只需修复一条树路径，而不是每次重排全部元素。

常见误解

• 堆数组不是从小到大排列，只保证父子关系。
• 修改元素优先级后不能什么都不做，必须重新调整或采用重新入队策略。
• 相同优先级的元素未必保持进入顺序；需要稳定性时加入递增序号作为第二排序键。

解决的问题

优先队列适合解决这类问题：等待区里的任务带有优先级，调度器需要快速取出当前优先级最高的一项。

普通做法可能是每次取的时候遍历一遍列表找最大值，复杂度是 O(n)。二叉堆把入队和出队控制在 O(log n)，适合元素持续进入、调度器持续取最大值的场景。提示消息是一个容易理解的教学例子，但是否真的按优先级显示，必须继续验证展示端消费的是 FIFO 还是堆。

核心结构

private readonly List<MessageConfig> _heap = new();

看起来只是一个 List，但它不是普通数组，而是把它当成一棵“隐式二叉树”。

对数组下标 i：

parent = (i - 1) / 2
left   = 2 * i + 1
right  = 2 * i + 2

举个例子，数组：

index:  0   1   2   3   4   5   6
value:  9   7   8   3   5   6   4

对应树：

        9
      /   \
     7     8
    / \   / \
   3   5 6   4

这里实现的是最大堆：父节点的优先级永远大于等于子节点。

所以堆顶 _heap[0] 永远是当前优先级最高的元素。

BubbleUp：入队过程

假设现在堆里已经有这些 Tips，数字代表 Priority：

_heap = [90, 70, 80, 30, 50, 60]

它对应的树是：

          90
        /    \
      70      80
     /  \    /
   30   50  60

现在插入一个新 Tips，优先级是 85。

第一步：先放到数组末尾。

_heap = [90, 70, 80, 30, 50, 60, 85]

树变成：

          90
        /    \
      70      80
     /  \    /  \
   30   50  60   85

新元素下标是 6。

根据公式：

parent = (i - 1) / 2
parent = (6 - 1) / 2 = 2

也就是它的父节点是下标 2，值是 80。

比较：

85 > 80

所以交换。

_heap = [90, 70, 85, 30, 50, 60, 80]

树变成：

          90
        /    \
      70      85
     /  \    /  \
   30   50  60   80

现在新元素来到下标 2。

继续找父节点：

parent = (2 - 1) / 2 = 0

父节点是 90。

比较：

85 <= 90

停。最大堆恢复完成。

所以 BubbleUp 的本质是：

新来的元素先坐最后一排；
如果它比上级优先级高，就一路往前换座位；
直到它不比父节点高，或者到达堆顶。

对应实现：

private void BubbleUp(int i)
{
    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (_heap[i].Priority <= _heap[parent].Priority) break;
        (_heap[i], _heap[parent]) = (_heap[parent], _heap[i]);
        i = parent;
    }
}

BubbleDown：出队过程

现在堆是：

_heap = [90, 70, 85, 30, 50, 60, 80]

树：

          90
        /    \
      70      85
     /  \    /  \
   30   50  60   80

出队时，要取出最高优先级，也就是 90。

第一步：保存堆顶。

top = 90

第二步：把最后一个元素 80 放到堆顶，然后删除最后一格。

_heap = [80, 70, 85, 30, 50, 60]

树暂时变成：

          80
        /    \
      70      85
     /  \    /
   30   50  60

现在违反了最大堆规则，因为 80 小于右孩子 85。

开始 BubbleDown。

当前位置 i = 0，左右孩子：

left  = 2 * 0 + 1 = 1 -> 70
right = 2 * 0 + 2 = 2 -> 85

左右孩子里最大的是 85，所以 80 和 85 交换。

_heap = [85, 70, 80, 30, 50, 60]

树变成：

          85
        /    \
      70      80
     /  \    /
   30   50  60

现在 80 到了下标 2。

继续找孩子：

left  = 2 * 2 + 1 = 5 -> 60
right = 2 * 2 + 2 = 6 -> 不存在

比较：

80 >= 60

停。最大堆恢复完成。

返回刚才保存的 top = 90。

对应实现：

private void BubbleDown(int i)
{
    int count = _heap.Count;
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < count && _heap[left].Priority > _heap[largest].Priority)
            largest = left;

        if (right < count && _heap[right].Priority > _heap[largest].Priority)
            largest = right;

        if (largest == i) break;

        (_heap[i], _heap[largest]) = (_heap[largest], _heap[i]);
        i = largest;
    }
}

这里最关键的一句是：

int largest = i;

它的意思不是“假设当前就是最大”，而是：

先把当前位置当作候选最大值；
再拿左孩子、右孩子分别挑战它；
最后谁最大，就让谁上去。

为什么不用普通队列

普通队列是先进先出：

入队顺序: A(10), B(100), C(30)
出队顺序: A, B, C

如果调度策略明确要求高优先级先处理，目标顺序才是：

出队顺序: B(100), C(30), A(10)

所以普通队列适合“顺序公平”，不适合“优先级调度”。

复杂度：

Enqueue: O(1)
Dequeue: O(1)
但不能快速拿最高优先级

为什么不每次排序

可以用排序列表，比如每次插入后排序：

插入 A(10) -> [10]
插入 B(100) -> [100, 10]
插入 C(30) -> [100, 30, 10]

取最高优先级很快，直接拿第一个。

但问题是：维护排序成本高。

常见复杂度：

插入后排序: O(n log n)
取最大值: O(1)
删除最大值: 如果删头部，可能 O(n)

如果用二分查找找到插入位置，查找是 O(log n)，但数组中间插入仍然要搬元素，所以整体还是 O(n)。

排序列表适合：

数据量不大；
或者插入很少，查询很多；
或者你需要完整有序遍历。

堆适合什么场景

堆的特点是：它不保证整个数组有序，只保证堆顶最大。

比如：

[90, 70, 85, 30, 50, 60, 80]

这不是完整降序数组，因为 80 在最后。

但它满足：

每个父节点 >= 自己的孩子

所以它能快速回答一个问题：

当前最高优先级是谁？

复杂度：

Enqueue: O(log n)
Dequeue: O(log n)
看堆顶: O(1)

堆适合：

Tips 优先级
任务调度
战斗 AI 行为选择
寻路 A* 的 open set
排行榜取 Top K
定时器系统取最近到期任务

从 FIFO 到堆调度：先确认消费点

提示系统可以分成四个角色：

生产者 → 等待区 → 调度器 → 活动区 → 到期回对象池

数据结构只有被调度器消费，才会改变用户看到的顺序。一个系统即使已经实现了最大堆，如果展示端仍从 FIFO 队列出队，优先级字段就不会影响显示。

当前可验证的提示链路使用两级 FIFO：

1. 入口 FIFO 汇聚并发到达的消息，并避免重复打开显示面板；
2. 面板 FIFO 依次取出消息，维护活动视图与对象池；
3. 已实现的最大堆没有接到这条消费链上。

因此，“当前提示按优先级显示”不是现状。最大堆更适合作为一次明确的调度演进。

三种可比较的策略

FIFO

比较键：arrivalSequence
出队：最早到达的消息

它保证顺序公平，入队和出队都是 O(1)，但高优先消息不能越过已经等待的低优先消息。

Priority-only heap

比较键：Priority
出队：最高优先级消息

入队和出队是 O(log n)。同优先级没有第二比较键，因此不保证先进先出。

Priority + sequence

先比较 Priority：越大越靠前
Priority 相同，再比较 Sequence：越小越靠前

这是教学中的稳定策略：保留优先级调度，同时让同级消息按到达顺序显示。它需要在消息进入等待区时分配单调递增序号。

不默认实现抢占与老化

以上策略只决定“下一条从等待区取谁”，不打断已经处于活动区的消息。

• 抢占：高优先消息是否立即替换正在显示的低优先消息；
• 老化：等待越久是否逐渐提高有效优先级；
• 防饥饿：低优先消息等待多久后必须获得机会。

这些都是独立的产品与调度策略，不能由“使用了堆”自动推导。本学习单元默认不实现抢占和老化，只观察等待顺序。

工程上可以补强的点

这个实现已经足够完整；如果继续扩展，可以加入一个 Peek：

public MessageConfig Peek()
{
    return _heap.Count == 0 ? null : _heap[0];
}

这样可以只看当前最高优先级，不弹出。

另外，如果两个 Tips 的 Priority 相同，现在谁先出并不稳定。

如果业务需要“同优先级先来先出”，可以给 MessageConfig 增加一个递增序号，比如 SequenceId，比较时变成：

Priority 越大越靠前；
Priority 相同，SequenceId 越小越靠前。

这就是工程里很常见的“主排序键 + 次排序键”。

最重要的收获

堆不是为了让全部元素有序。

堆是为了用更低成本维护“当前最值”。

很多数据结构的选择，不是问“它能不能做”，而是问：

我最频繁的问题是什么？
我愿意把成本花在插入、删除、查询的哪一步？