【算法】贪心+堆排序实现大根堆及标准库容器类的融合使用
📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨
文章目录
- 📢前言
- 🏳️🌈一、什么是贪心
- 🏳️🌈二、大根堆算法概述
- 🏳️🌈三、深入剖析大根堆实现细节
- 🏳️🌈四、标准库容器类的融合使用
- ❤️一、vector 与 set
- 🧡二、vector与map
- 💛三、list与queue
- 💚四、deque与stack
- 💙
- 👥总结
📢前言
先看题
这个算法，是要通过循环找到所有元素中最大的那个偶元素，对其除以2，然后再找这之后的最大的那个偶元素以此类推
笔者的经历不多，第一次做的时候没有想到 大根堆 的算法，只是用 sort 将每次除以2后的整个数组进行降序排序，这样的作法
- 使用
sort对数组进行排序后，虽然可以确定数组中的元素大小顺序，但在每次选择偶数进行减半操作时，需要遍历整个数组来找到合适的偶数，效率较低。 - 对于一个较大的数组，排序后可能需要花费较多的时间来找到下一个要进行减半操作的偶数，尤其是当操作次数较多时，这种遍历的方式会变得非常耗时。
这不符合贪心的要求，但使用 大根堆 的方法，在进行操作的过程中，能够实时地根据当前数组的状态进行调整。每次操作后，只需要对受影响的元素进行堆的调整操作，时间复杂度相对较低。
因此这题代码解析如下
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
int main()
{
int n, k;
cin >> n >> k;
priority_queue<LL> heap; // 优先队列，可以理解为大根堆
LL tmp;
LL ans = 0;
for (int i = 0; i < n; i++)
{
cin >> tmp;
ans += tmp;
if (tmp % 2 == 0)
heap.push(tmp);
}
while (k-- && !heap.empty())
{
LL t = heap.top() / 2;
ans -= t;
heap.pop();
if (t % 2 == 0) heap.push(t);
}
printf("%lld", ans);
return 0;
}
🏳️🌈一、什么是贪心
贪心算法是一种在每一步选择中都采取当前状态下的最优决策的算法设计策略。
贪心算法有以下几个特点：
一、局部最优选择
在每一步决策时，贪心算法总是选择当前看起来最优的选项，而不考虑整体的最优解是否一定能够通过这些局部最优选择得到。这种局部最优选择是基于某种特定的贪心策略，例如选择当前价值最大的物品、选择距离最近的节点等。
例如，在找零钱问题中，如果要使用最少的硬币找零，贪心策略可能是每次选择面值尽可能大的硬币。比如要找零 63 元，有 1 元、5 元、10 元、20 元、50 元的硬币，贪心算法会先选择一个 50 元硬币，然后再选择一个 10 元硬币，接着选择一个 1 元、1 元、1 元硬币，共使用了五枚硬币。
二、不一定得到全局最优解
虽然贪心算法在很多情况下能够快速得到一个可行解，但它不能保证一定能得到全局最优解。这是因为贪心算法只考虑了局部最优，而没有考虑到所有可能的情况。
例如，在背包问题中，如果物品可以分割，使用贪心算法按照物品的单位价值（价值/重量）从大到小选择物品放入背包，可能会得到一个接近最优解的结果，但不一定是全局最优解。而对于 0-1 背包问题（物品不可分割），贪心算法通常不能得到最优解。
三、适用性和高效性
贪心算法适用于一些具有特定性质的问题，这些问题通常具有贪心选择性质和最优子结构性质。贪心选择性质是指通过局部最优选择可以得到全局最优解的一个必要条件；最优子结构性质是指问题的最优解可以由子问题的最优解组合而成。
贪心算法通常比较简单直观，实现起来相对容易，并且在很多情况下具有较高的效率。因为它不需要进行复杂的搜索和回溯，只需要在每一步做出一个局部最优选择即可。
总的来说，贪心算法是一种在特定问题中能够快速得到可行解的算法策略，但需要谨慎使用，并且在使用时需要分析问题是否满足贪心选择性质和最优子结构性质，以确保得到的解是合理的。
🏳️🌈二、大根堆算法概述
（一）贪心算法与大根堆
贪心算法在大根堆构建中有着巧妙的运用。以力扣中的一些问题为例，比如在解决可达到最远建筑问题时，贪心算法通过局部最优解的选择，逐步逼近全局最优解。在大根堆 + 贪心算法的场景中，如神偷 Jacky 在楼顶穿梭的问题，当遇到下一个楼顶大于当前楼顶爬不上去的时候，优先选择丢砖头，保留梯子以备更需要的时候使用。这体现了贪心算法在大根堆构建中的思想，即每次选择当前最优的决策，以达到最终的目标。
（二）队列结合大根堆
队列可以与大根堆结合，实现优先级队列等功能。例如在手机上玩游戏的时候，如果有来电，系统应该优先处理打进来的电话，这就引入了优先级队列这种数据结构。例如在解决最优的方式安排会议问题时，按照会议结束时间建立比较器，将会议放入小顶堆；循环所有会议，符合限制开始时间时结果加一，然后限制开始时间后移到当前会议的结束时间。
（三）堆排序实现大根堆
堆排序在构建大根堆过程中有着重要的作用。大根堆就是对于每一个元素，它的值大于等于它的孩子节点。大根堆保存在一个数组中，第 0 个元素作为堆的根。堆排序主要分为两步：
- 构建大根堆和调整大根堆。构建大根堆时我们是自底向上的进行比较，使得每次构建的堆都是大根堆；
- 当构建完毕后，每次则是自顶向下的进行比较，保证形成新的大根堆。
例如在对一个无序数列进行递增排序时，先按照完全二叉树的层序顺序，插入叶子结点，然后比较该叶子结点与其父结点，如果比父结点大，则与父结点交换，此时可以保证当前的子树是大根堆。重复这个过程，直到所有数都添加至这个树中，完成大根堆的构建。接着进行调整大根堆的操作，将根结点与树中最后一个结点进行交换，并将这个最大值剔除这个树，对剩下的数进行调整，自顶向下的进行判断，如果根结点比两个孩子结点的最大值要小，则把最大值与根结点交换，重复这个过程，直到这个树为空，此时我们可以得到一个有序的数列。
🏳️🌈三、深入剖析大根堆实现细节
在考试时我们可以直接使用库函数 queue 中的 priority_queue 优先队列来实现大根堆，但是因为我们要充分理解大根堆的实现方式我们
- 堆的概念：堆是一颗完全二叉树，若根节点索引从 0 开始编号，对于大根堆，若：Ki >= K2i+1 且 Ki >= K2i+2，i =0，1，2…，则称为大堆。将根节点最大的堆叫做最大堆或大根堆。
- 存储方式：堆是一颗完全二叉树，因此可以采用顺序方式进行存储。对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
- 创建过程：给定一个任意整型数组，将其调整为最大堆。核心思路是从最后一个非叶子节点开始进行元素下沉操作，不断向根节点倒着向下调整，慢慢的将左右子树调整为最大堆。
// 模拟实现 priority_heap
template<typename T>
class my_priority_heap // 优先队列，大根堆
{
public:
// 尾插，实现自动大根堆
void push(T val)
{
heap.push_back(val);
adjustup(heap.size() - 1);
}
// 获得堆顶的值
T top()
{
if (heap.size() == 0)
return T();
return heap[0];
}
// 头删，实现自动大根堆
void pop()
{
if (heap.size() == 0)
return;
heap[0] = heap.back();
heap.pop_back();// vector 在创建的时候可能会开辟空间，不能直接 size-- 会造成内存泄漏
adjustdown(0);
}
// swap 实现
void swap(int i, int j)
{
T tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
private:
vector<T> heap;
int parent(int index) { return (index - 1) / 2; }// 方法 - 获得父节点
int leftchild(int index) { return (index * 2) + 1; } // 方法 - 获得左子节点
int rightchild(int index) { return (index * 2) + 2; } // 方法 - 获得右子节点
// 向上调整
void adjustup(int index)
{
if (index > 0 && (heap[index] > heap[parent(index)]))
{
swap(index, parent(index));
index = parent(index);
adjustup(index);
}
}
// 向下调整
void adjustdown(int index)
{
int largest = index;
int left = leftchild(index);
int right = rightchild(index);
if (left < heap.size() && heap[left] > heap[largest]) largest = left;
if (right < heap.size() && heap[right] > heap[largest]) largest = right;
if (largest != index)
{
swap(heap[largest], heap[index]);
adjustdown(largest);
}
}
};
🏳️🌈四、标准库容器类的融合使用
在这里大根堆的模拟实现是利用了 vector 和 heap 两种容器，实现了有队列的删对头，填队尾的能力，也就是优先队列
可见标准库容器是可以融合使用贯通的，以此来达到某种目的
举几个例子
❤️一、vector 与 set
- 数据去重与排序：
可以先使用vector存储数据，然后将其内容复制到set中。由于set的特性是自动排序且不允许重复元素，这样可以快速实现对数据的去重和排序。
示例代码：
std::vector<int> vec = {3, 1, 2, 3, 4, 1};
std::set<int> s(vec.begin(), vec.end());
// s 现在是 {1, 2, 3, 4}，已排序且无重复元素。
- 高效查找与随机访问结合：
如果需要频繁进行随机访问，可以使用vector。而当需要快速查找特定元素是否存在时，可以利用set。
例如，在处理大量数据时，可以先将数据存储在vector中，然后根据需要在特定操作中使用set进行快速查找。
🧡二、vector与map
- 关联数据存储与快速访问：
vector可以存储一系列数据，而map可以建立数据之间的关联关系。例如，可以用vector存储对象列表，然后用map建立对象的某个属性与对象在vector中的索引的映射，以便快速根据属性值查找对应的对象。
示例代码：
std::vector<Person> people;
people.push_back(Person("Alice", 25));
people.push_back(Person("Bob", 30));
std::map<std::string, int> nameToIndex;
for (int i = 0; i < people.size(); ++i) {
nameToIndex[people[i].name] = i;
}
int index = nameToIndex["Bob"];
if (index!= -1) {
std::cout << "Bob's age is " << people[index].age << std::endl;
}
💛三、list与queue
- 灵活的链表操作与队列行为：
list提供了高效的插入和删除操作，可以作为底层存储结构。然后，可以通过封装list来实现一个具有队列行为的容器，例如使用push_back在尾部插入元素，使用pop_front在头部删除元素，模拟队列的先进先出（FIFO）特性。
示例代码：
std::list<int> dataList;
// 模拟队列操作
dataList.push_back(1);
dataList.push_back(2);
dataList.push_back(3);
while (!dataList.empty()) {
int frontElement = dataList.front();
std::cout << frontElement << " ";
dataList.pop_front();
}
💚四、deque与stack
- 双端队列作为栈使用：
deque支持在两端进行高效的插入和删除操作。可以将deque封装成一个栈，只在一端进行插入（push_back）和删除（pop_back）操作，实现栈的后进先出（LIFO）特性。
示例代码：
加粗样式
💙
👥总结
本篇博文对 大根堆 及 标准库容器类的融合使用 做了一个较为详细的介绍，不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧！会继续努力的~
