作为最小堆应用,实现了另一个实用的类----优先队列.优先队列有着广泛的应用,在操作系统中,许多消息队列、等待队列等,使用了优先队列,在算法中,我们常用优先队列来实现广度搜索、贪心算法等。
Priority_Queue.h
#include"MinHeap.h"
template<class T>
class Priority_Queue{
public:
Priority_Queue();
~Priority_Queue();
void Push(const T &x);
T Pop();
bool IsEmpty();
bool IsFull();
private:
MinHeap<T> *m_heap;
const int maxSize;
};
template<class T>
Priority_Queue<T>::Priority_Queue():maxSize(100){
m_heap = new MinHeap<T>(maxSize);
}
template<class T>
Priority_Queue<T>::~Priority_Queue(){
delete m_heap;
}
template<class T>
void Priority_Queue<T>::Push(const T &x){
m_heap->Insert(x);
}
template<class T>
T Priority_Queue<T>::Pop(){
T temp;
m_heap->RemoveMin(temp);
return temp;
}
template<class T>
bool Priority_Queue<T>::IsEmpty(){
return m_heap->IsEmpty();
}
template<class T>
bool Priority_Queue<T>::IsFull(){
return m_heap->IsFull();
}
mainApp.cpp测试文件:
#include<iostream>
#include"Priority_Queue.h"
using namespace std;
void main(){
int a[5] = {3,2,1,4,5};
int i;
Priority_Queue<int> p_queue;
for(i = 0; i < 5; i++){
p_queue.Push(a[i]);
}
while(!p_queue.IsEmpty()){
cout<<p_queue.Pop()<<" ";
}
cout<<endl;
}
分享到:
相关推荐
+ [单调队列](#单调队列) + [哈希表](#哈希表) + [Splay](#splay) * [图论](#图论) + [图论](#图论-1) + [模型建立](#模型建立) + [网络流](#网络流) + [最短路](#最短路) + [欧拉路](#欧拉路) + [差分...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度...
12.5.1 高度优先与宽度优先的最大及最小左高树 12.5.2 最大HBLT的插入 12.5.3 最大HBLT的删除 12.5.4 两棵最大HBLT的合并 12.5.5 初始化 12.5.6 类maxHblt 12.6 应用 12.6.1 堆排序 12.6.2 机器调度 12.6.3 霍夫曼...
数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,二斜堆,二项堆,二叉查找树,红黑树,AVL平衡树,Treap,Splay,静态二叉查找树,2-d树,...
优先队列搜索,过最少的门救人,建图 A*搜索 图论 差分约束 Intervals bellman_ford Intervals SPFA 出纳员的雇佣 不等式组 图论 割边 图染色 拓扑 树 欧拉路径) 割点+统计删除后剩下多少连通图 删除一个点...
第三章 栈和队列 第一节 栈 第二节 栈的应用举例 第三节 队列 第四节 栈和队列的应用举例 第四章 多维数组和广义表 第一节 多维数组和运算 第二节 矩阵的压缩存储(默认按行优先存储) 第三节 广义表基础 第五章 树...
6.5 优先队列 思考题 本章注记 第7章 快速排序 7.1 快速排序的描述 7.2 快速排序的性能 7.3 快速排序的随机化版本 7.4 快速排序分析 7.4.1 最坏情况分析 7.4.2 期望运行时间 思考题 ...
前端工程师常用数据结构、算法和资源的列表。 数据结构 堆 队列 链表 哈希表 套 特里 堆 树 二叉搜索树 广度优先搜索 (BFS) 深度优先搜索 (DFS) 预排序(根、左、右):序列化/反序列化 中序(左、根、右):BST 0->...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...
2.4 优先队列 2.4.1 API 2.4.2 初级实现 2.4.3 堆的定义 2.4.4 堆的算法 2.4.5 堆排序 2.5 应用 2.5.1 将各种数据排序 2.5.2 我应该使用哪种排序算法 2.5.3 问题的归约 2.5.4 排序应用一览 第3章 查找 ...
第9章 优先队列 276 9.1 引言 276 9.2 线性表 277 9.3 堆 278 9.3.1 定义 278 9.3.2 最大堆的插入 279 9.3.3 最大堆的删除 279 9.3.4 最大堆的初始化 280 9.3.5 类MaxHeap 281 9.4 左高树 285 9.4.1 高度与宽度优先...