首页 - 资讯 - 科技 - 教育 - 汽车 - 财经 - 健康 - 房产 - 文旅 - 娱乐 - 游戏
科研 |知识 |母婴 |养生 |美食 |幼教 |高考 |大学 |就业 |锐评 |培训 |数码 |互联网 |名企 |IT业 |能源
当前位置： 首页> 健康> 母婴 > 装修网站哪家靠谱_站酷设计网站官网入口免费_二级域名查询入口_网络营销渠道

装修网站哪家靠谱_站酷设计网站官网入口免费_二级域名查询入口_网络营销渠道

时间:2025/7/9 17:00:26来源：https://blog.csdn.net/ycs66/article/details/145553803 浏览次数:0次
装修网站哪家靠谱_站酷设计网站官网入口免费_二级域名查询入口_网络营销渠道

目录

  • 一、二叉堆的核心思想与本质
  • 二、二叉堆的实现与操作
    • 1. 存储结构
    • 2. 基本操作
  • 三、二叉堆的应用场景
    • 1. 优先队列
    • 2. Top-K 问题
    • 3. 堆排序
    • 4. 中位数维护
  • 四、二叉堆的复杂度分析
  • 五、二叉堆的变种与高阶应用
    • 1. 二项堆
    • 2. 斐波那契堆
    • 3. 左偏堆
  • 六、常见陷阱与调试技巧
    • 1. 边界条件处理
    • 2. 调试方法
  • 七、代码模版（c++）
  • 八、经典例题
    • 小蓝的最大集合
    • 第k大的数
    • 一道简单的取模问题
  • 九、总结与学习建议
    • 1. 核心总结
    • 2. 学习建议

在这里插入图片描述

一、二叉堆的核心思想与本质

核心思想：二叉堆是一种完全二叉树，满足堆性质（父节点的值总是大于或小于子节点的值）。

最大堆：父节点的值大于或等于子节点的值。

最小堆：父节点的值小于或等于子节点的值。

本质：通过维护堆性质，实现高效的插入、删除和最值查询操作。

二、二叉堆的实现与操作

1. 存储结构

数组存储：利用完全二叉树的性质，将堆存储在一维数组中。

对于下标为 i 的节点：

父节点：(i - 1) / 2

左子节点：2 * i + 1

右子节点：2 * i + 2

2. 基本操作

插入（Insert）：
将新元素插入数组末尾。
从新元素开始向上调整（上浮），直到满足堆性质。

删除堆顶（Extract-Max/Min）：

将堆顶元素与数组末尾元素交换。
删除末尾元素。
从堆顶开始向下调整（下沉），直到满足堆性质。

建堆（Heapify）：
从最后一个非叶子节点开始，依次向下调整。

三、二叉堆的应用场景

1. 优先队列

实现优先级调度：每次取出优先级最高的元素。

示例：Dijkstra 算法中用于选择最短路径。

2. Top-K 问题

问题描述：从大量数据中找出前 K 个最大或最小的元素。

解法：使用最小堆维护前 K 个最大元素，或使用最大堆维护前 K 个最小元素。

3. 堆排序

步骤：
建堆。
依次将堆顶元素与末尾元素交换，并调整堆。

时间复杂度：
O(nlogn)。

4. 中位数维护

问题描述：动态维护数据流的中位数。

解法：使用一个最大堆和一个最小堆，分别存储较小的一半和较大的一半。

四、二叉堆的复杂度分析

时间复杂度
插入：
O(logn)

删除堆顶：
O(logn)

建堆：

O(n)（通过数学证明，建堆的摊还复杂度为 O(n)）

堆排序：
O(nlogn)

空间复杂度
存储堆：
O(n)

五、二叉堆的变种与高阶应用

1. 二项堆

特点：由多个二项树组成，支持高效的合并操作。

应用：图算法中的优先级队列。

2. 斐波那契堆

特点：支持更高效的插入、合并和减小键值操作。

应用：Dijkstra 算法和 Prim 算法。

3. 左偏堆

特点：支持高效的合并操作，适合需要频繁合并堆的场景。

六、常见陷阱与调试技巧

1. 边界条件处理

空堆检查：在删除堆顶前需判断堆是否为空。

数组越界：在调整堆时注意下标范围。

2. 调试方法

打印堆状态：在每次操作后输出堆的内容。

可视化堆结构：手动画出堆的树形结构，检查堆性质。

七、代码模版（c++）

#include<iostream>
using namespace std;#define maxn 100001
#define lson(idx)(idx*2+1)
#define rson(idx)(idx*2+2)
#define parent(idx)((idx-1)/2)template<typename T>
struct Small{bool operator()(const T& left, const T& right) const {return left < right;}
};template<typename T>
struct Big {bool operator()(const T& left, const T& right) const {return left > right;}
};template<class T,typename cmp>
class Heap {
private:void shiftUp(int curr);void shiftDown(int curr);
public:Heap(int cap = maxn);~Heap();void push(const T& data);void pop();T top() const;bool empty() const;void clear();
private:T* m_data;int m_size;int m_capacity;cmp m_cmp;
};template<class T, typename cmp>
void Heap<T, cmp>::shiftUp(int curr){if (curr == 0)return;int par = parent(curr);if (m_cmp(m_data[curr], m_data[par])) {swap(m_data[curr], m_data[par]);shiftUp(par);}}template<class T, typename cmp>
void Heap<T, cmp>::shiftDown(int curr){int lsonId = lson(curr);int rsonId = rson(curr);int optId = curr;if (lsonId < m_size && m_cmp(m_data[lsonId], m_data[optId])) {optId = lsonId;}if (rsonId < m_size && m_cmp(m_data[rsonId], m_data[optId])) {optId = rsonId;}if (curr != optId) {swap(m_data[optId], m_data[curr]);shiftDown(optId);}
}template<class T, typename cmp>
Heap<T, cmp>::Heap(int cap){m_data = new T[cap];m_capacity = cap;m_size = 0;
}template<class T, typename cmp>
Heap<T, cmp>::~Heap(){delete[] m_data;m_data = NULL;
}template<class T, typename cmp>
void Heap<T, cmp>::push(const T& data){m_data[m_size++] = data;shiftUp(m_size - 1);
}template<class T, typename cmp>
void Heap<T, cmp>::pop(){swap(m_data[0], m_data[m_size - 1]);m_size--;shiftDown(0);
}template<class T, typename cmp>
T Heap<T, cmp>::top() const{return m_data[0];
}template<class T, typename cmp>
bool Heap<T, cmp>::empty() const{return m_size == 0;
}template<class T, typename cmp>
void Heap<T, cmp>::clear(){m_size = 0;
}int main() {Heap<int, Big<int>> h;for (int i = 0; i < 5; i++) {int x = rand() % 30;int y = rand() % 30;h.push(x), h.push(y);cout << "塞入两个数：" << x << ' ' << y << endl;cout << "目前最大的数是" << h.top() << endl;h.pop();cout << "弹出最大的那个数" << endl;}return 0;
}

八、经典例题

小蓝的最大集合

#include<iostream>
using namespace std;#define maxn 200001
#define lson(idx)(idx*2+1)
#define rson(idx)(idx*2+2)
#define parent(idx)((idx-1)/2)template<typename T>
struct Small {bool operator()(const T& left, const T& right) const {return left < right;}
};template<typename T>
struct Big {bool operator()(const T& left, const T& right) const {return left > right;}
};template<class T,typename cmp>
class Heap {
private:void shiftUp(int curr);void shiftDown(int curr);T* m_data;int m_size;int m_capacity;cmp m_cmp;
public:Heap(int cap=maxn);~Heap();void push(const T& data);void pop();T top() const;void clear();bool empty() const;int size();T* getData();
};template<class T, typename cmp>
void Heap<T, cmp>::shiftUp(int curr){if (curr == 0)return;int par = parent(curr);if (m_cmp(m_data[curr], m_data[par])) {swap(m_data[par], m_data[curr]);shiftUp(par);}
}template<class T, typename cmp>
void Heap<T, cmp>::shiftDown(int curr) {int lsonId = lson(curr);int rsonId = rson(curr);int optId = curr;if (lsonId < m_size && m_cmp(m_data[lsonId], m_data[optId])) {optId = lsonId;}if (rsonId < m_size && m_cmp(m_data[rsonId], m_data[optId])) {optId = rsonId;}if (curr != optId) {swap(m_data[curr], m_data[optId]);shiftDown(optId);}
}template<class T, typename cmp>
Heap<T, cmp>::Heap(int cap) {m_size = 0;m_data = new T[cap];m_capacity = cap;
}template<class T, typename cmp>
Heap<T, cmp>::~Heap() {m_size = 0;delete[] m_data;m_data = NULL;
}template<class T, typename cmp>
void Heap<T, cmp>::push(const T& data) {m_data[m_size++] = data;shiftUp(m_size - 1);
}template<class T, typename cmp>
void Heap<T, cmp>::pop() {swap(m_data[0], m_data[m_size - 1]);m_size--;shiftDown(0);
}template<class T, typename cmp>
T Heap<T, cmp>::top() const {return m_data[0];
}template<class T, typename cmp>
void Heap<T, cmp>::clear() {m_size = 0;
}template<class T, typename cmp>
bool Heap<T, cmp>::empty() const {return m_size == 0;
}template<class T, typename cmp>
int Heap<T, cmp>::size() {return m_size;
}template<class T, typename cmp>
T* Heap<T, cmp>::getData() {return m_data;
}int main() {Heap<int, Big<int>> h;int n, k;cin >> n >> k;h.push(k);while (n--) {int opt;cin >> opt;if (opt == 1) {int x;cin >> x;h.push(x);}else if (opt == 2) {int x;cin >> x;int* data = h.getData();for (int i = 0; i < h.size(); i++) {data[i] += x;}}else if (opt == 3) {int x;cin >> x;int* data = h.getData();for (int i = 0; i < h.size(); i++) {data[i] -= x;}}else {cout << h.top() << endl;h.pop();}}cout << endl;return 0;
}

还有一种方法

Heap<int, Big<int>> h;
int n, k;
cin >> n >> k;
h.push(k);
int sum = 0;		//用于记录数字串中被加减后的值
while (n--) {int opt;cin >> opt;if (opt == 4) {cout << h.top() + sum << endl;h.pop();}else {int x;cin >> x;if (opt == 1) {h.push(x - sum);}else if (opt == 2) {sum += x;}else if (opt == 3) {sum -= x;}}
}
cout << endl;

第k大的数

#include<iostream>
using namespace std;#define maxn 200001
#define lson(idx)(idx*2+1)
#define rson(idx)(idx*2+2)
#define parent(idx)((idx-1)/2)template<typename T>
struct Small {bool operator()(const T& left, const T& right) const {return left < right;}
};template<typename T>
struct Big {bool operator()(const T& left, const T& right) const {return left > right;}
};template<class T,typename cmp>
class Heap {
private:void shiftUp(int curr);void shiftDown(int curr);T* m_data;int m_size;int m_capacity;cmp m_cmp;
public:Heap(int cap=maxn);~Heap();void push(const T& data);void pop();T top() const;void clear();bool empty() const;int size();T* getData();
};template<class T, typename cmp>
void Heap<T, cmp>::shiftUp(int curr){if (curr == 0)return;int par = parent(curr);if (m_cmp(m_data[curr], m_data[par])) {swap(m_data[par], m_data[curr]);shiftUp(par);}
}template<class T, typename cmp>
void Heap<T, cmp>::shiftDown(int curr) {int lsonId = lson(curr);int rsonId = rson(curr);int optId = curr;if (lsonId < m_size && m_cmp(m_data[lsonId], m_data[optId])) {optId = lsonId;}if (rsonId < m_size && m_cmp(m_data[rsonId], m_data[optId])) {optId = rsonId;}if (curr != optId) {swap(m_data[curr], m_data[optId]);shiftDown(optId);}
}template<class T, typename cmp>
Heap<T, cmp>::Heap(int cap) {m_size = 0;m_data = new T[cap];m_capacity = cap;
}template<class T, typename cmp>
Heap<T, cmp>::~Heap() {m_size = 0;delete[] m_data;m_data = NULL;
}template<class T, typename cmp>
void Heap<T, cmp>::push(const T& data) {m_data[m_size++] = data;shiftUp(m_size - 1);
}template<class T, typename cmp>
void Heap<T, cmp>::pop() {swap(m_data[0], m_data[m_size - 1]);m_size--;shiftDown(0);
}template<class T, typename cmp>
T Heap<T, cmp>::top() const {return m_data[0];
}template<class T, typename cmp>
void Heap<T, cmp>::clear() {m_size = 0;
}template<class T, typename cmp>
bool Heap<T, cmp>::empty() const {return m_size == 0;
}template<class T, typename cmp>
int Heap<T, cmp>::size() {return m_size;
}template<class T, typename cmp>
T* Heap<T, cmp>::getData() {return m_data;
}int main() {Heap<int, Small<int>> h;int n, k;cin >> n >> k;for (int i = 0; i < n; i++) {int a;cin >> a;h.push(a);}while (k--) {int x;cin >> x;if (x >= h.top()) {h.pop();h.push(x);}cout << h.top() << ' ';}cout << endl;return 0;
}

一道简单的取模问题

#include<iostream>
using namespace std;#define maxn 200001
#define lson(idx)(idx*2+1)
#define rson(idx)(idx*2+2)
#define parent(idx)((idx-1)/2)template<typename T>
struct Small {bool operator()(const T& left, const T& right) const {return left < right;}
};template<typename T>
struct Big {bool operator()(const T& left, const T& right) const {return left > right;}
};template<class T,typename cmp>
class Heap {
private:void shiftUp(int curr);void shiftDown(int curr);T* m_data;int m_size;int m_capacity;cmp m_cmp;
public:Heap(int cap=maxn);~Heap();void push(const T& data);void pop();T top() const;void clear();bool empty() const;int size();T* getData();
};template<class T, typename cmp>
void Heap<T, cmp>::shiftUp(int curr){if (curr == 0)return;int par = parent(curr);if (m_cmp(m_data[curr], m_data[par])) {swap(m_data[par], m_data[curr]);shiftUp(par);}
}template<class T, typename cmp>
void Heap<T, cmp>::shiftDown(int curr) {int lsonId = lson(curr);int rsonId = rson(curr);int optId = curr;if (lsonId < m_size && m_cmp(m_data[lsonId], m_data[optId])) {optId = lsonId;}if (rsonId < m_size && m_cmp(m_data[rsonId], m_data[optId])) {optId = rsonId;}if (curr != optId) {swap(m_data[curr], m_data[optId]);shiftDown(optId);}
}template<class T, typename cmp>
Heap<T, cmp>::Heap(int cap) {m_size = 0;m_data = new T[cap];m_capacity = cap;
}template<class T, typename cmp>
Heap<T, cmp>::~Heap() {m_size = 0;delete[] m_data;m_data = NULL;
}template<class T, typename cmp>
void Heap<T, cmp>::push(const T& data) {m_data[m_size++] = data;shiftUp(m_size - 1);
}template<class T, typename cmp>
void Heap<T, cmp>::pop() {swap(m_data[0], m_data[m_size - 1]);m_size--;shiftDown(0);
}template<class T, typename cmp>
T Heap<T, cmp>::top() const {return m_data[0];
}template<class T, typename cmp>
void Heap<T, cmp>::clear() {m_size = 0;
}template<class T, typename cmp>
bool Heap<T, cmp>::empty() const {return m_size == 0;
}template<class T, typename cmp>
int Heap<T, cmp>::size() {return m_size;
}template<class T, typename cmp>
T* Heap<T, cmp>::getData() {return m_data;
}int main() {Heap<int, Big<int>> h;int n, q;cin >> n >> q;long long sum = 0;for (int i = 0; i < n; i++) {int a;cin >> a;sum += a;h.push(a);}while (q--) {int x;cin >> x;while (!h.empty()) {if (h.top() >= x) {sum -= h.top();int y = h.top() % x;sum += y;h.pop();h.push(y);}else break;}cout << sum << ' ';}cout << endl;return 0;
}

九、总结与学习建议

1. 核心总结

二叉堆的核心是利用完全二叉树和堆性质实现高效的最值操作。

高阶问题的突破口通常在于堆的变种（如二项堆、斐波那契堆）或堆的应用场景（如优先队列、Top-K 问题）。

2. 学习建议

分类刷题：按问题类型集中练习（如优先队列、堆排序、Top-K 问题）。

对比其他数据结构：理解二叉堆与平衡二叉树的异同。

手写模拟过程：在纸上画出堆的调整过程，加深直观理解。

在这里插入图片描述

希望大家可以一键三连，后续我们一起学习，谢谢大家！！！

在这里插入图片描述

关键字：装修网站哪家靠谱_站酷设计网站官网入口免费_二级域名查询入口_网络营销渠道

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

责任编辑：
>> 相关文章
>> 热门图片
网站制作费用及后期运营_展厅设计方案100例_百度竞价收费标准_seo按照搜索引擎的什么对网站
网站制作费用及后期运营_展厅设计方案100例_百度竞价收费标准_seo按照搜索引擎的什么对网站
百度云网站入口_网站设置密码进入_锦州seo推广_网上培训课程平台
百度云网站入口_网站设置密码进入_锦州seo推广_网上培训课程平台
中国东方营销网站_北京新冠最新情况最新消息_东莞seo优化公司_免费建站哪个比较好
中国东方营销网站_北京新冠最新情况最新消息_东莞seo优化公司_免费建站哪个比较好
banner免费设计网站_长沙网站优化方案_口碑营销的成功案例_代写平台在哪找
banner免费设计网站_长沙网站优化方案_口碑营销的成功案例_代写平台在哪找
公司网站的推广方案_无锡网页设计制作_百度网站电话是多少_免费发布产品信息的网站
公司网站的推广方案_无锡网页设计制作_百度网站电话是多少_免费发布产品信息的网站
深圳疫情防控发布会_十大电商平台有哪些_seo刷关键词排名优化_安全又舒适的避孕方法有哪些
深圳疫情防控发布会_十大电商平台有哪些_seo刷关键词排名优化_安全又舒适的避孕方法有哪些
长图海报制作网站_转让公司哪个平台比较快_友情链接属于免费推广吗_2000元代理微信朋友圈广告
长图海报制作网站_转让公司哪个平台比较快_友情链接属于免费推广吗_2000元代理微信朋友圈广告
域名怎么买_西安大雁塔疫情_排名第一的玉米品种_怎么发帖子做推广
域名怎么买_西安大雁塔疫情_排名第一的玉米品种_怎么发帖子做推广
>> 热门搜索
评论排行
图片新闻
更多>>
装修网站哪家靠谱_站酷设计网站官网入口免费_二级域名查询入口_网络营销渠道
江苏省镇江市丹徒区疫情最新消息_中国疫情突然没了_网站提交百度收录_seo结算系统
面试经典 222. 完全二叉树的节点个数
石家庄疫情不敢公布_抖音直播开放平台_seo排名优化推广教程_百度网页游戏
点击排行

邮箱：809451989@qq.com 网站地图
未经过本站允许,请勿将本站内容传播或复制