程序员学数据结构

第10章　堆：有序树

堆（heap）是一类特殊的树结构，它的次序由树中每个节点的值或相关的键值所决定。若堆的顺序为升序，则该堆为最小堆，其根节点的值或优先级小于它的子节点。若堆的顺序为降序，则该堆为最大堆，其根节点的值或优先级大于它的子节点。应注意的是，不能将堆结构与计算机科学领域中的堆内存相混淆，堆内存通常指系统动态分配的内存。

本章将涵盖以下主要内容：

• 堆结构的定义；
• 基于数组的实现；
• 堆的构建；
• 基本操作。

10.1　堆的实现

堆结构与树结构类似，通常使用链表、链接节点或数组对其进行实现。在第9章中，我们已经讨论过链接节点的实现方式，本章将会着重讲解使用数组对二叉堆（binaryheap）这种堆结构来进行实现。

二叉堆是一种特殊的树结构，该结构除了最深的那一层外，其余每层都会被节点占满。而在最深的那一层，节点会从左到右排列，直到占满整层。图10-1展示了一个基于数组的二叉堆实现，该二叉堆中的每个父节点都有两个分别位于2i+1和2i+2的子节点，其中为这个父节点的序号，而数据集中的第一个节点的序号为0。

图10-1

另一种实现方式会跳过数组中序号0的位置，用以简化查找给定序号的父节点和子节点的过程。在这种情况下，若给定的节点位于i，其子节点的序号分别为2i和2i +1。