优先队列(priority_queue)的粗略实现_带带我咯的博客-程序员秘密

技术标签: 学习  笔记  堆排序  队列  数据结构  queue  

优先队列的实现:
原理:优先队列实质上就是一个堆,只要掌握了堆的基础知识实现:大顶堆、小顶堆、递归调整顶堆,实现优先队列不在话下。STL中的优先队列默认大顶堆,也可以通过一定的方法变为小顶堆。我实现的优先队列暂时只能默认大顶堆,当然本来就是为了练习 ’ 堆 ’ 这一数据结构罢了。自己动手实现一些STL中的数据结构往往会有一些不错的收获。

头文件模板:

#pragma once
template <class T>
class MyPriority_Queue {
    
private:
	T *root;
	int curSize;//当前尺寸
	int capacity;//总容量
	void resize(int newSize) {
    //重新分配内存(扩容、缩容)
		T *newHeap = new T[newSize];
		for (int i = 0; i < curSize; i++) {
    
			newHeap[i] = root[i];
		}
		delete[] root;
		root = newHeap;
		capacity = newSize;
	}
	void swap(T &a, T &b) {
    //交换
		T temp = a^b;
		a = temp^a;
		b = temp^b;
	}
public:
	MyPriority_Queue() {
    
		root = new T[10];
		capacity = 10;
		curSize = 0;
	}
	~MyPriority_Queue() {
    
		delete[] root;
	}
	MyPriority_Queue(int newSize) {
    
		root = new T[newSize * 2];
		capacity = newSize * 2;
		curSize = 0;
	}
	void push(T e) {
    //入队
		if (curSize == capacity) {
    
			resize(capacity * 2);
		}
		root[curSize] = e;
		curSize++;
		for (int i = curSize / 2 - 1; i >= 0; i--) {
    //从最后的非叶子节点开始(下标从零开始)
			adjustHeap(i);
		}
	}
	void pop() {
    //出队(退出堆顶元素)
		if (curSize == 0) {
    
			throw out_of_range("Wrong!");
		}
		if (curSize > 1)
			swap(root[0], root[curSize - 1]);
		curSize--;
		if (curSize <= capacity / 4) {
    
			resize(capacity / 2);
		}
		adjustHeap(0);//从头开始调整
	}
	T top()const {
    //返回堆顶元素
		if (curSize == 0) {
    
			throw out_of_range("Wrong!");
		}
		return root[0];
	}
	void adjustHeap(int index) {
    //大根堆
		int left = index * 2 + 1;
		int right = left + 1;
		if (left >= curSize) return;

		int mxindex = index;
		if (left<curSize&&root[left]>root[mxindex]) {
    
			mxindex = left;
		}
		if (right<curSize&&root[right]>root[mxindex]) {
    
			mxindex = right;
		}
		if (mxindex != index) {
    
			swap(root[index], root[mxindex]);
			adjustHeap(mxindex);//交换后当前节点的叶子结点可能被影响了,递归的进行调整
		}
	}
	bool empty() {
    
		if (curSize == 0) return true;
		return false;
	}
	int size() {
    
		return curSize;
	}
};

使用优先队列简单的进行数组排序进行测试:

#include<iostream>
#include"MyPriority_Queue.h"
using namespace std;
MyPriority_Queue<int> q;
int main() {
    //优先队列实现从大到小排序
	int arr[10] = {
     8,15,0,3,6,19,21,25,5,2 };
	for (int i = 0; i < 10; i++) {
    
		q.push(arr[i]);
	}
	int i = 0;
	cout << "尺寸:" << q.size() << '\n';
	while (!q.empty()) {
    
		arr[i++] = q.top();
		q.pop();
	}
	for (i = 0; i < 10; i++) {
    
		cout << arr[i] << ' ';
	}
	return 0;
}

就这样吧,不是很难~

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_54069398/article/details/115188693

智能推荐

定时器实现方式_yun2008yun的博客-程序员秘密_handle实现定时器

1、Handler + Thread (利用的Thread的sleepI(long)接口)2、Handler的postDelayed(Runnable, long)接口3、采用Handler与java的Timer 及 TimerTask 结合的方法采用Handler 和 Thread的sleep(long)方法 handler 主要用来处理接收到的信息(分发+处理),当然其

easyexcel使用问题处理_芊芊寻的博客-程序员秘密_easyexcel常见问题

项目中有处理excel文件需求,之前用过poi和jxl,两者处理文档的速度很快,但jxl无法处理07及以上版本的excel,而poi经常出现outofmemory错误,了解到阿里有一个开源的easyexcel可以解决poi中的oom问题,所以在项目中尝试使用easyexcel替代poi。传送门:easyexcel在实际使用过程中发现有几个地方有些小问题,一是当07版本excel文件中有多个shee...

winform学习(9)Timer控件_b4834988的博客-程序员秘密

利用Timer控件制作简单的跑马灯:拉一个Lable控件至窗体中心,Text内容为★★★★再拉一个Timer控件,属性Enabled设置为True(即开启控件),Interval设置为100(单位为ms)双击Timer控件进入默认Tick事件方法private void timer1_Tick(object sender, System.EventArgs...

SWT Browser_Helen_Happy的博客-程序员秘密

-Dorg.eclipse.swt.browser.DefaultType=webkit指定浏览器类型

Linux(Ubuntu)常用命令总结--Linux Command CheatSheet_YukinoSiro的博客-程序员秘密

最近看到一份非常不错的linux常用命令总结,适合于刚入门的新手原地址:https://rumorscity.com/wp-content/uploads/2014/08/10-Linux-Unix-Command-Cheat-Sheet-021.jpg 

ios网络模拟和抓包_杨宗卫的爸爸的博客-程序员秘密

ios网络模拟和抓包Posted on 2014-12-17 by iPanda最近在鼓捣ios的传文件,离不开抓包分析和网络模拟,找到两种方式抓包、网络模拟方式分别对应ios模拟器(使用mac的NetworkLinkConditioner配置mac系统的网络模拟)+wireshark;另一种是使用rvictl工具对真机抓包(真机,我就不用网络模拟了)。下面详细说一下:

随便推点

Hadoop Mapreduce任务出错,Child Error_iteye_10418的博客-程序员秘密

集群出现大面积任务失败,表现为mapreduce刚启动不久,就抛出异常,查看log可以看到,Status : FAILEDjava.lang.Throwable: Child Errorat org.apache.hadoop.mapred.TaskRunner.run(TaskRunner.java:271)Caused by: java.io.IOException: Task...

vim 配置及ctag cscope_雨林水枫的博客-程序员秘密

1. 平时都是使用source insight软件进行编辑和查看代码,当代码量巨大或者代码在server上时,使用source insight会比较慢,或者直接崩溃,如果配置好vim在加上ctag 一些插件,使用起来会方便的多,也看个人习惯,不要求熟练,个人觉得需要会用一些2. vim的配置文件~/.vimrc中map :!ctags -R --c++-kinds=+p --fiel

在Ubuntu系统中重置root密码_寰宇001的博客-程序员秘密_ubuntu重置root密码

对于现代人,特别是年轻人,都有过忘记密码的经历吧。在这篇文章中,我们来了解如何在 Ubuntu 18.04 LTS 和 Ubuntu 20.04 中重置忘记的 root 密码。首先,你需要开机或重启你的 Ubuntu 系统。你需要先进入 GRUB 菜单,如果你的系统是在 VirtualBox 上运行,按键盘上的 SHIFT 调出启动菜单。然后,按 e 键来编辑 GRUB 参数,将会显示如下的界面:往下滚动,找到以 ‘linux /boot/vmlinuz’ 开始的一行,已在下图中标记出来:找到

7个很棒的JavaScript产品引导库_杭州程序员张张的博客-程序员秘密

1. Intro.js介绍Intro.js 由于其用户友好的解决方案而被广泛使用,并拥有1.9万个GitHub star。其最重要的功能是:无依赖项:不需要任何其他依赖项体积小,速度快:体积较小,因此引导过程顺畅而直观。JavaScript文件的总大小为10KB, CSS为2.5KB。用户友好:导航是用户友好的,并提供可根据您的喜好选择的各种主题。浏览器兼容性:可在所有主要浏览器上...

linux 下 php 安装扩展_一遇一余的博客-程序员秘密_linux 安装php扩展

1、 下载需要的php操作redis的扩展包 (1)、切换到 cd / 根目录 (2)、下载phpredis wget https://github.com/nicolasff/phpredis/archive/2.2.4.tar.gz (https://github.com/nicolasff/phpredis ,这个手动下载并上传到服务器,然后用unzip xxxx进行解压,下面步骤一样) 后面这个地址适合于php7 (3)、 tar -zxvf 2...

mac系统使用vscode插件code runner运行python出现SyntaxError: invalid syntax错误_Elpcoin的博客-程序员秘密

mac系统下使用vscode插件code runner运行python出现SyntaxError: invalid syntax错误mac 自带 python2 在未设置的code runner默认使用python2运行 ,导致一些python3的语法不支持改成python3 即可

推荐文章

热门文章

相关标签