本文共 1017 字，大约阅读时间需要 3 分钟。

堆数据结构

堆是一种基于完全二叉树的数据结构，具有以下特点：每个节点的值总是不大于或不小于其父节点的值。一棵深度为k且有n个结点的二叉树称为满二叉树，而深度为k且有n个结点的二叉树称为完全二叉树。

堆的分类

堆可分为大顶堆和小顶堆两种类型：

• 大顶堆：每个节点的值都大于或等于其子节点的值。
• 小顶堆：每个节点的值都小于或等于其子节点的值。

大顶堆和小顶堆都可用于从小到大或从大到小排序，通常选择大顶堆进行排序。

堆的代码实现

堆可以用数组来实现，数组元素对应树的节点索引。父子节点的索引关系如下：

• 索引为t的节点，其父节点索引为 (t - 1) / 2。
• 索引为t的节点，其左孩子索引为 2t + 1，右孩子索引为 2t + 2。

插入操作（push）

删除操作（pop）

堆排序

堆排序是一种选择排序算法，利用堆数据结构实现。其基本思想如下：

这种方法的时间复杂度为 O(n log n)，是不稳定的排序算法。

C++11中的优先队列

在C++11中，priority_queue 是一种优先队列容器适配器，默认以最大值优先。其成员函数包括：

• top()：访问队头元素。
• empty()：判断队列是否为空。
• size()：返回队列元素个数。
• push()：插入元素并排序。
• pop()：删除队头元素。
• swap()：交换队列内容。

优先队列的定义形式为：

priority_queue
   

其中：

• Type 为数据类型，默认为大顶堆。
• Container 为容器类型（需支持数组操作，如 vector）。
• Functional 为比较函数，用于定义优先级规则。

小顶堆可通过传递 greater<Type> 比较函数定义。

总结

堆数据结构作为完全二叉树的应用，广泛用于排序、优先级队列等场景。其插入和删除操作通过对数组的直接操作实现，时间复杂度为 O(log n)。C++11中的 priority_queue 提供了便捷的优先队列接口，适用于多种应用场景。