优先队列(堆)是一种非传统的数据结构，它不止用来存储数据，而且使数据排列具有一定的性质和规律，使其便于在数据中找到最具优先权的一个。

本文介绍堆的性质、实现和应用，以及相关操作时间复杂度的计算。

堆模型

堆具有插入(Push)和删除(Pop)两种基本操作，插入将一个数据放入堆中，删除操作会找出、删除堆中的最大或最小元素。在后面我们会看到，堆往往用数组进行实现，它的逻辑结构是一棵完全二叉树，物理结构是一个数组，根据成立条件，堆主要分为两种类型：

• 大根堆，所有节点的值大于或等于其子节点的值
• 小根堆，所有节点的值小于或等于其子节点的值

堆的实现

在讨论堆的实现之前，需要先了解二叉树的实现，这里讨论二叉树的两种实现方法：数组实现和链式实现。用数组实现二叉树时，考虑用数组存储二叉树每一层的值，此时会遇到一个问题，即当二叉树某节点的左子树或右子树为空时，会存在不可避免的空间浪费现象，当一棵树非常不平衡时，这个缺陷就格外突出。但是用数组实现数据较为紧凑的完全二叉树就极为合适。

链表实现

如果用链表来实现堆，可以用头插的方式以常数时间实现插入数据，但是要找出最大或最小的数据的时间复杂度是O(N)；或者时刻保持链表有序，此时找出最大或最小的数据的时间复杂度是O(1)，但插入数据需要线性时间。下面介绍一个更高效的实现方法，其插入和删除的复杂度均为O(logN)，这一点在下文会给出证明。

数组实现

上文说到，一棵完全二叉树完全适合用数组实现，用数组实现堆是最普遍的方法。用数组实现的堆(二叉堆)不仅可以有效地存储数据，而且各个数据索引之间存在的数学关系可以让我们方便地找出二叉树节点的父亲或孩子，这点在讨论堆的性质时会提到。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* pHp, HPDataType* a, int n);
// 堆的销毁
void HeapDestry(Heap* pHp);
// 堆的插入
void HeapPush(Heap* pHp, HPDataType x);
// 堆的删除
void HeapPop(Heap* pHp);
// 取堆顶的数据
HPDataType HeapTop(Heap* pHp);
// 堆的数据个数
int HeapSize(Heap* pHp);
// 堆的判空
bool HeapEmpty(Heap* pHp);

二叉堆的性质

堆具有两个性质：结构性和堆序性。

结构性质

堆是一棵完全二叉树，一个高为 h 的堆

可得排序部分的时间复杂度为 O(n*logn)。

综上，堆排序的总体时间复杂度由排序部分所决定，为O(n*log)。