c++实现一个堆-包含插入删除获取
2023-02-18 16:41:45 时间
堆不要求整个数组有序,只需要关注堆顶,和堆排序不一样
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class MYHEAP {
public:
void push(int val) { //插入到末尾,往前调整
nums.push_back(val);
heapUp();
}
void pop() { //删除堆顶,往后调整
nums[0] = nums.back();
nums.pop_back();
heapDown();
}
void heapUp() //插入元素,从后往前调整
{
int index = nums.size() - 1;
int father = (index - 1) / 2;
while (index > 0) {
if (nums[index] < nums[father]) {
swap(nums[index], nums[father]);
index = father;
father = (father - 1) / 2;
}
else {
break;
}
}
}
void heapDown() //删除堆顶,从0往后调整
{
int index = 0;
int max_index = nums.size() - 1;
int lchild=0;
int rchild;
while (index < max_index) {
lchild = 2 * index + 1;
rchild = 2 * index + 2;
if (lchild > max_index) break; //不存在左孩子
else if (rchild > max_index) { //存在左孩子,不存在右孩子
if (nums[index] > nums[lchild]) {
swap(nums[index], nums[lchild]);
index = lchild;
}
else {
break;
}
}
else { //左右孩子都存在
int smaller = nums[lchild] <= nums[rchild] ? lchild : rchild;
if (nums[index] > nums[smaller]) {
swap(nums[index], nums[smaller]);
index = smaller;
}
else {
break;
}
}
}
}
void getTop() {
cout << nums[0]<<endl;
}
private:
vector<int> nums;
};
int main() {
vector<int> nums = { 2,1,6,4,3,7,0,11 };
MYHEAP heap;
for (int i = 0; i < 6; i++) {
heap.push(nums[i]);
heap.getTop();
}
heap.pop();
heap.getTop();
}
关于堆排序的文章在这里
相关文章
- [Linux] docker 方式安装和使用gitlab-ce
- [Linux] 使用mount来挂载设备到目录
- [Linux] SSH隧道本地端口转发访问远程服务中的数据库
- [Linux] 纯净ubuntu系统仓库更换为阿里云的源
- [Linux] deepin系统添加PHP仓库源出错Error: could not find a distribution template for Deepin/stable
- [视频教程] 如何在Linux深度系统deepin下安装docker
- 4种Golang并发操作中常见的死锁情形
- Linux如何进行GPIO读写操作的?
- [Linux] 编写Dockerfile文件自动构建镜像
- [Linux] nginx的try_files指令实现隐藏index.php的重写
- [linux] shell脚本编程-统计日志文件中的设备号发通知邮件
- [Linux]F5负载均衡器
- [Go] golang设置运行的cpu数
- [Go] golang的MPG调度模型
- [Linux] 进程间通信
- [linux] 多进程和多线程
- [linux] 进程五状态模型
- Linux系统日志介绍
- Linux系统账户后门及排查
- [Go] golang的用途和windows搭建环境