文章目录
- 堆
- 堆的代码实现
- 堆排序
- C++11 中的堆 priority_queue
堆 堆 Heap 这种数据结构其实就是一颗 “完全二叉树”，每个节点的值总是不大于或不小于其父节点的值：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。一棵深度为k且有 个结点的二叉树称为 “满二叉树”。
文章图片
堆的分类：
- 大顶堆：每个节点的值都大于或等于其子节点的值
- 小顶堆：每个节点的值都小于或等于其子节点的值
文章图片
堆的代码实现 堆就是一颗完全二叉树，中间没有空洞，因此可以使用内存连续的数组或动态数组来实现。以大顶堆为例。
先将堆中结点的序号和数组索引进行对应：（与层次遍历类似）
文章图片
显然，每对父子结点在数组中的索引存在数学关系：
- 索引为t t t 的结点，其父结点索引为( t ? 1 ) / 2 (t-1)/2 (t?1)/2
- 索引为t t t 的结点，其左孩子索引为t × 2 + 1 t×2+1 t×2+1，右孩子索引为t × 2 + 2 t×2+2 t×2+2
- 先将元素插入到最后一个结点
- 由此逐层向上渗透：若比父结点大，就交换
文章图片
- 先将根节点删除，替换为最后一个结点
- 由此逐层向下渗透：若比左右结点小，就和bigger交换
文章图片
#pragma once
#include template
class MaxHeap
{
public:
MaxHeap() {}
~MaxHeap() {}
void push(T& x);
void pop();
bool empty() const;
const T& top() const;
//private:
std::vector heap;
};
template
inline void MaxHeap::push(T& x)
{
// 添加元素
heap.push_back(x);
// 向上渗透
int index = heap.size() - 1;
while (index > 0)
{
int parent = (index - 1) / 2;
if (heap[parent] >= x) break;
heap[index] = heap[parent];
index = parent;
}
heap[index] = x;
}template
inline void MaxHeap::pop()
{
// 替换根结点
T x = heap[0] = heap[heap.size() - 1];
heap.pop_back();
if (heap.empty()) return;
// 向下渗透
int index = 0;
while (index * 2 + 1 < heap.size()) // 左子结点存在
{
int larger_child;
int l_child = index * 2 + 1;
int r_child = index * 2 + 2;
if (r_child < heap.size() && heap[r_child] >= heap[l_child])// 右子结点存在
{
larger_child = r_child;
}
else
{
larger_child = l_child;
}
if (x > heap[larger_child])// 截止
break;
heap[index] = heap[larger_child];
index = larger_child;
}
heap[index] = x;
}template
inline bool MaxHeap::empty() const
{
return heap.empty();
}template
inline const T& MaxHeap::top() const
{
return heap[0];
}
堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为O(nlogn)，是不稳定排序。
基本思想：
- 构造一个空的大顶堆；
- 将待排序序列
push进入大顶堆，此时，整个序列的最大值就是堆顶的根节点 - 将大顶堆的根节点反复读出、删除即得到有序序列
#include
#include "MaxHeap.h"using namespace std;
int main(int argc, char* argv[])
{
int a[10] = { 11,3,25,177,299,0,52,74,86,308 };
int n = 10;
MaxHeap heap;
for (auto x : a)
{
heap.push(x);
}cout << "从小到大：";
for (int i = n-1;
i >=0;
i--)
{
a[i] = heap.top();
heap.pop();
}//cout << "从大到小：";
//for (int i = 0;
i < n;
i++)
//{
//a[i] = heap.top();
//heap.pop();
//} // 输出排序结果
for (int i = 0;
i < n;
i++)
cout << a[i] << ", ";
cout << endl;
return 0;
}
C++11 中的堆 priority_queue 优先队列是一种容器适配器，默认第一个元素总是保持最大，内部类似于堆结构。提供常数时间的最大元素（默认）查找，对数代价的插入与删除(二分法)。
成员函数：
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列(并排序)
- pop 弹出队头元素
- swap 交换内容
priority_queue- Type 就是数据类型
- Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
- Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入
【C++|Data Structures in C++（堆和堆排序）】小顶堆定义：
priority_queue < int, vector, greater > q;
推荐阅读
- c++堆排序和堆
- c++|一文读懂 Android FFmpeg 视频解码过程与实战分析
- python|【Rust日报】2022-03-22 fluent-uri（一个快速、简单和严格的URI解析器）
- c++|【Rust日报】2022-03-23 RustSBI软件发布v0.2.2版本
- 嵌入式|【Rust 日报】2021-11-21 The RustFest Global - Rust in Arts
- 蓝桥杯|蓝桥python—— 剪邮票【2016 第七题】
- 备战蓝桥杯|【蓝桥python冲刺17天】——如何轻松拿捏必考数论题（（第三弹））
- C/C++气象数据中心实战，手把手教你做工业级项目吾爱fen享
- c++语言入门一本通|【信息学奥赛】2054（【例3.4】适合晨练（C++））