第2章　改进优先队列：d叉堆

本章主要内容

●　解决如何处理基于优先级的任务的问题

●　用优先队列来解决上述问题

●　用堆来实现优先队列

●　介绍并分析d叉堆

●　识别能通过堆来提高性能的用例

我们在第1章中介绍了一些关于数据结构和编程技术的基本概念，也介绍了本书内容的组织理念。现在，你应该知道为什么开发人员都需要了解数据结构了。

在本章中，我们将深入探讨上述内容并加以完善。我们将围绕一个有一定算法背景的读者都十分熟悉的主题展开介绍，还将回顾堆的知识，并就分支因子给出一些新的见解。

基于上述目标，我们假设你已经熟悉CS 101课程（计算机入门课）中通常都会讲解的一些基本概念，如大O符号、RAM模型，以及诸如数组、列表、树这样的基础数据结构。在本书中，我们将利用这些“组件块”来构建更复杂的数据结构和算法。熟悉这些概念对于你学习后面的章节也是非常重要的，为此我们在附录中也给出了相关的概述。

在2.1节中，我们将描述后续各章都会用到的“本章结构”。然后在2.2节介绍你在本章中遇到的问题（如何有效地处理具有优先级的事件），在2.3节概述优先队列这种可能的解决方案，并阐释为什么优先队列要比那些基础的数据结构更好。

随后，我们将在2.4节描述优先队列的API[1]，并在2.5节和2.6节深入研究其内部结构之前，先把它作为黑匣子，然后通过一个示例来展示如何使用它。我们将在2.5节详细分析d叉堆的工作原理及其各个方法的功能，并在2.6节深入研究d叉堆的实现。

---

[1]　应用程序接口（Application Programming Interface，API）。

在2.7节和2.8节，我们将通过一些其他用例来展示堆和优先队列是如何发挥作用并提升应用程序或其他算法的性能的。

在2.9节，我们将重点介绍堆的最佳分支因子。你可以将2.9节作为选读内容，不过至少应该通读一遍，以深入了解堆的工作原理，以及什么时候该选择三叉堆，什么时候又该选择二叉堆。

本章内容较多，可能会让你望而生畏，但请坚持下去，以便为后续的学习夯实基础。