如果我们有$N$个数据，希望找到其中最大的$M$个，该怎么做？或许你想到了排序，时间复杂度为$O(NlogN)$，空间复杂度为$O(N)$，当$N$很大的时候，这并不是一个好的选择。一个更好的方法是使用优先队列（堆）。

我们可以写出如下代码：

MinPQ<Integer> pq = new MinPQ<>();
while (!StdIn.isEmpty()) {
    int num = StdIn.readInt();
    pq.insert(num);
    if (pq.size() > M)
        pq.delMin();
}

这样，时间复杂度便降到了$O(NlogM)$，空间复杂度降为$O(M)$。

优先队列还有其他许多应用，常见的有数据压缩，图的搜索，事件驱动仿真等。本文主要讨论其中的两个应用：事件驱动仿真、A*搜索算法，后者也就是完成本周assignment的关键。

事件驱动仿真

时间驱动与事件驱动

仿真有两种常见的方法，一为时间驱动（time-driven），二为事件驱动（event-driven）。

时间驱动

概述：系统以固定的时间间隔dt往前运行，每次时间间隔后检查是否已有事件发生，若有则作出相应的处理。

优点：实现简单。

缺点：dt若过大，可能会略过了事件的发生；dt若太小，又会有过多的无用检查。

事件驱动

概述：系统预测该时间点后各个事件发生的时间，然后每次将时间推进到最近将发生的事件，作出相应处理，再预测以后事件的发生。

优点：由于两个相邻事件之间的时间内系统状态不会发生改变，所以系统时间可以直接从一个事件发生的时间推进到下一个事件发生的时间，这样也就不会又多余的检查。

缺点：实现较为复杂。

事件驱动的构件（ingredients）

事件的优先队列
因为优先队列（堆）这一数据结构可以快速提取到最近将发生的事件。
事件的循环（预测+处理）
每次提取出最近将发生的事件，时间推进到那一刻并作出处理，再进行预测，直至优先队列为空。

样例：Collision system

这里以碰撞系统为例来讨论仿真，我们的目标是根据弹性碰撞的规律，模拟$N$个物体在方盒中的运动情况。详细的介绍与物理公式见coursera上的lecture slides。

时间驱动？

若我们使用时间驱动，那么我们每次在时间间隔dt后，都需要大约$1/2N^2$次的碰撞检查。且如前所述，dt取的很小的话仿真会很慢，取得很大的话又可能错过某次碰撞。

事件驱动？

若我们使用事件驱动，就不会有以上的烦恼，因为系统的状态仅会在碰撞发生时改变。实现的核心在于完成碰撞的预测及处理。

预测

已知了物体的速度、质量、半径与位置，只需利用高中物理的公式就可以计算出当前物体与其余物体以及墙碰撞的时间。

处理

碰撞发生后，我们需要改变碰撞物体的速度（还是用高中物理的公式），再以此速度去预测与其他物体以及墙碰撞的时间。

A*算法 & Assignment: 8 Puzzle

关于A*算法，之前在图论：常用的最短路算法详解这篇博客就已经详细讨论过了，在这里我们只是讨论这次的assignment是如何将A*算法应用到8 puzzle上的。

我们可以将这一问题映射到图的搜索过程：

出发点：初始给定的板
目的地：以行为序的板
出发点到当前点的距离：初始板到当前板的移动次数
当前点到目的地的距离：
- 汉明距离（hamming）：板上对应块值却不同的个数（不包括空块）
- 曼哈顿距离（manhattan）：当前板上各个块到目标板上对应值的块的距离之和
优先级：出发点到当前点的距离+当前点到目标点的距离