优先队列简单介绍：
操作系统表明上看着是支持多个应用程序同一时候执行。其实是每一个时刻仅仅能有一个进程执行，操作系统会调度不同的进程去执行。
每一个进程都仅仅能执行一个固定的时间，当超过了该时间。操作系统就会暂停当前执行的进程，去调度其他进程来执行。
实现这样的进程调度的一种方法是使用队列。
開始的时候进程被放在队列的末尾，调度程序将重复提取队列中的第一个进程来执行。直到执行完成或时间片用完，若进程没有执行完成则将该进程放入队列的末尾。这样的策略不是特别合适，由于可能一些短的进程须要等待非常长的时间才干轮流到。一般来说，执行时间短的进程须要尽快的结束。所以那些执行时间短的进程须要比較高的优先权，相同，那些比較重要的进程也须要比較高的优先权。
这样的特殊的应用须要一种特殊的队列-----优先队列。能够用二叉堆实现优先队列。二叉堆简单介绍：
二叉堆与二叉查找树类似，二叉树有两个性质：结构性质和堆序性质。
结构性质：
二叉堆是一棵全然二叉树，除了子节点外的其他节点都有两个儿子节点。 一棵高为h的全然二叉树有2^h到2^(h+1) - 1个节点。全然二叉树的高为log(N)，N为节点数目。
因为全然二叉树的特点，实现起来非常easy，用简单的数组就能够实现。对于数组中的任何位置i上的元素，其左儿子在位置2*i上，右儿子在(2*i)+1上，其父节点在i/2上（让根节点在位置1）。
以下是一棵全然二叉树的数组实现图示：
堆序性质：
由于假设想高速找到最小单元。则最小单元应该在根上。在堆中，对于每个节点x,x的值大于等于子节点（叶子节点除外）；没有二叉查找树的要求严格。二叉堆的数据结构实现：
用一个数组 vector<Comparable> v;来存储全部的元素。 用currentSize来记录当前元素的数目。
vectorarray;//存储二叉堆的节点 int currentSize;//当前二叉堆中的节点数目
二叉堆的主要成员函数：
bool isEmpty() const;//推断二叉堆是否为空const Comparable & findMin() const;//查找最小元素void insert(const Comparable & x);//插入元素xvoid deleteMin();//删除最小元素void deleteMin(Comparable & minItem);//删除最小元素，并以引用的方式返回该最小元素void makeEmpty();//清空该二叉堆 void print() const;//打印该堆元素void buildHeap();//将元素移动到合适的位置void percolateDown(int hole);//下移动
二叉堆的主要成员函数介绍：
1、插入insert()：
比方：当插入14的时候。第一步在堆的下一个可用的位置建立空穴。假设在该空穴插入14后满足堆序性，则插入成功。 但当在该空穴插入14之后不满足堆序性，则将该空穴的父节点移入空穴，之前的父节点的位置变为了空穴。 然后再尝试插入该新的空穴，假设不满足堆序。则反复之前的操作。
/***************************************************************** 函数名称：insert(const Comparable & x)* 功能描写叙述: 删除最小元素* 參数列表: 无* 返回结果：void *****************************************************************/templatevoid BinaryHeap ::insert(const Comparable & x){ if(currentSize == array.size()-1) array.resize(2 * array.size());//扩大堆中数组的容量 //获得空穴的位置 int hole = ++currentSize; //上滤 for(; hole > 1 && x < array[hole/2]; hole /= 2) array[hole] = array[hole/2]; //将x插入到合适的位置 array[hole] = x;}
2、删除最小元素deleteMin()：
将堆中最小的一个元素删除之后（最下的元素位于堆数组的最前面）。必须将堆中最后一个元素x移动到堆中的某个合适的位置。.
比方:在下图中删除最小元素的操作。 删除最小元素13。将最后一个元素31移动到13的位置；31比13的两个孩子的值都大，全部将两个孩子值比較小的上移动。所以将14上移动。然后31再和14的两个孩子的值比較。直到31比空穴的两个孩子的值都小，或者是空穴到了叶子节点。则直接将31插入到空穴。
/***************************************************************** 函数名称：deleteMin()* 功能描写叙述: 删除最小元素* 參数列表: 无* 返回结果：void *****************************************************************/templatevoid BinaryHeap ::deleteMin(){ if(isEmpty()){ cout << "BinaryHeap is empty." << endl; return; } array[1] = array[currentSize];//将最后一个元素移动到最小元素的位置 currentSize--;//元素总数减去1 //将最后一个元素移动到合适的位置 percolateDown(1); }/***************************************************************** 函数名称：percolateDown(int hole)* 功能描写叙述: 将array(hole)处的值向下移动 * 參数列表: hole为堆中元素的位置标号* 返回结果：void *****************************************************************/template void BinaryHeap ::percolateDown(int hole){ int child; //先保存array[hole]的值 Comparable temp = array[hole]; for(; hole * 2 <= currentSize; hole = child){ child = hole * 2; //child != currentSize,表明此时空穴有右儿子 //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子 if(child != currentSize && array[child] > array[child+1]) child++;//此时child表示为空穴的右儿子 //空穴的右儿子小于array[hole] if(array[child] < temp) array[hole] = array[child]; else break; } array[hole] = temp;}
以下是main函数，主要是对散列表类进行測试。
//測试主函数int main(){ srand(unsigned(time(0))); BinaryHeap binaryHeap; vector v; for(int i = 0; i < 10; ++i) v.push_back(rand() % 10); cout << "v: "; for(int i = 0; i < 10; ++i) cout << v[i] << " "; cout << endl; for(int i = 0; i < 10; ++i) binaryHeap.insert(v[i]); binaryHeap.print(); for(int i = 0; i < 12; i++){ int minVal = 0; binaryHeap.deleteMin(minVal); cout << "删除最小元素：" << minVal << endl; binaryHeap.print(); } cout << "*****************************************" << endl; cout << "測试第二个构造函数: " << endl; BinaryHeap binaryHeap2(v); binaryHeap2.print(); for(int i = 0; i < 12; i++){ int minVal = 0; binaryHeap2.deleteMin(minVal); cout << "删除最小元素：" << minVal << endl; binaryHeap2.print(); } return 0;} 以下是二叉堆类的源码：
/************************************************************************* > File Name: binaryHeap.cpp > Author: > Mail: > Created Time: 2016年04月14日 星期四 11时37分43秒 ************************************************************************/#include#include #include #include using namespace std;/******************************************* 类的名称：二叉堆******************************************/template class BinaryHeap{ public: explicit BinaryHeap(int capacity = 100):array(capacity), currentSize(0){} explicit BinaryHeap(const vector & items); bool isEmpty() const;//推断二叉堆是否为空 const Comparable & findMin() const;//查找最小元素 void insert(const Comparable & x);//插入元素x void deleteMin();//删除最小元素 void deleteMin(Comparable & minItem);//删除最小元素。并以引用的方式返回该最小元素 void makeEmpty();//清空该二叉堆 void print() const;//打印该堆元素 private: vector array;//存储二叉堆的节点 int currentSize;//当前二叉堆中的节点数目 private: void buildHeap();//将元素移动到合适的位置 void percolateDown(int hole);//下移动};/***************************************************************** 函数名称：print() const* 功能描写叙述: 打印该堆元素 * 參数列表: 无 * 返回结果：无*****************************************************************/template void BinaryHeap ::print() const{ cout << "二叉堆的元素: " << endl; for(int i = 1; i <= currentSize; ++i) cout << array[i] << " "; cout << endl;}/***************************************************************** 函数名称：BinaryHeap(const vector & items)* 功能描写叙述: 构造函数* 參数列表: items 是构造二叉堆须要的数据* 返回结果：无*****************************************************************/template BinaryHeap ::BinaryHeap(const vector & items):array(items.size()+10), currentSize(items.size()){ for(unsigned i = 0; i < items.size(); ++i) array[i+1] = items[i]; buildHeap();}/***************************************************************** 函数名称：buildHeap()* 功能描写叙述: 将元素移动到合适的位置，满足堆序* 參数列表: 无* 返回结果：void*****************************************************************/template void BinaryHeap ::buildHeap(){ for(int i = currentSize / 2; i > 0; --i) percolateDown(i);}/***************************************************************** 函数名称：findMin()* 功能描写叙述: 查找最小元素* 參数列表: 无* 返回结果：返回最小元素的引用*****************************************************************/template const Comparable & BinaryHeap ::findMin() const{ return array[1]; }/***************************************************************** 函数名称：insert(const Comparable & x)* 功能描写叙述: 删除最小元素* 參数列表: 无* 返回结果：void *****************************************************************/template void BinaryHeap ::insert(const Comparable & x){ if(currentSize == array.size()-1) array.resize(2 * array.size());//扩大堆中数组的容量 //获得空穴的位置 int hole = ++currentSize; //上滤 for(; hole > 1 && x < array[hole/2]; hole /= 2) array[hole] = array[hole/2]; //将x插入到合适的位置 array[hole] = x;}/***************************************************************** 函数名称：deleteMin()* 功能描写叙述: 删除最小元素* 參数列表: 无* 返回结果：void *****************************************************************/template void BinaryHeap ::deleteMin(){ if(isEmpty()){ cout << "BinaryHeap is empty." << endl; return; } array[1] = array[currentSize];//将最后一个元素移动到最小元素的位置 currentSize--;//元素总数减去1 //将最后一个元素移动到合适的位置 percolateDown(1); }/***************************************************************** 函数名称：percolateDown(int hole)* 功能描写叙述: 将array(hole)处的值向下移动 * 參数列表: hole为堆中元素的位置标号* 返回结果：void *****************************************************************/template void BinaryHeap ::percolateDown(int hole){ int child; //先保存array[hole]的值 Comparable temp = array[hole]; for(; hole * 2 <= currentSize; hole = child){ child = hole * 2; //child != currentSize,表明此时空穴有右儿子 //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子 if(child != currentSize && array[child] > array[child+1]) child++;//此时child表示为空穴的右儿子 //空穴的右儿子小于array[hole] if(array[child] < temp) array[hole] = array[child]; else break; } array[hole] = temp;}/***************************************************************** 函数名称：deleteMin(Comparable & minItem)* 功能描写叙述: 删除最小元素* 參数列表: minItem 将最小元素赋值给引用minItem* 返回结果：void *****************************************************************/template void BinaryHeap ::deleteMin(Comparable & minItem){ if(isEmpty()){ cout << "binaryHeap is empty." << endl; return; } minItem = array[1]; array[1] = array[currentSize--]; percolateDown(1);}/***************************************************************** 函数名称：makeEmpty()* 功能描写叙述: 情况二叉堆* 參数列表: 无* 返回结果：void *****************************************************************/template void BinaryHeap ::makeEmpty(){ currentSize = 0;}/***************************************************************** 函数名称：isEmpty()* 功能描写叙述: 推断二叉堆是否为空* 參数列表: 无* 返回结果：假设为空，则返回true。否则返回false*****************************************************************/template bool BinaryHeap ::isEmpty() const{ return currentSize == 0;}//測试主函数int main(){ srand(unsigned(time(0))); BinaryHeap binaryHeap; vector v; for(int i = 0; i < 10; ++i) v.push_back(rand() % 10); cout << "v: "; for(int i = 0; i < 10; ++i) cout << v[i] << " "; cout << endl; for(int i = 0; i < 10; ++i) binaryHeap.insert(v[i]); binaryHeap.print(); for(int i = 0; i < 12; i++){ int minVal = 0; binaryHeap.deleteMin(minVal); cout << "删除最小元素：" << minVal << endl; binaryHeap.print(); } cout << "*****************************************" << endl; cout << "測试第二个构造函数: " << endl; BinaryHeap binaryHeap2(v); binaryHeap2.print(); for(int i = 0; i < 12; i++){ int minVal = 0; binaryHeap2.deleteMin(minVal); cout << "删除最小元素：" << minVal << endl; binaryHeap2.print(); } return 0;}
以下是程序的执行结果：
v: 5 3 8 4 3 6 1 5 4 5 二叉堆的元素: 1 3 3 4 4 8 6 5 5 5 删除最小元素：1二叉堆的元素: 3 4 3 5 4 8 6 5 5 删除最小元素：3二叉堆的元素: 3 4 5 5 4 8 6 5 删除最小元素：3二叉堆的元素: 4 4 5 5 5 8 6 删除最小元素：4二叉堆的元素: 4 5 5 6 5 8 删除最小元素：4二叉堆的元素: 5 5 5 6 8 删除最小元素：5二叉堆的元素: 5 6 5 8 删除最小元素：5二叉堆的元素: 5 6 8 删除最小元素：5二叉堆的元素: 6 8 删除最小元素：6二叉堆的元素: 8 删除最小元素：8二叉堆的元素: binaryHeap is empty.删除最小元素：0二叉堆的元素: binaryHeap is empty.删除最小元素：0二叉堆的元素: *****************************************測试第二个构造函数: 二叉堆的元素: 1 3 5 4 3 6 8 5 4 5 删除最小元素：1二叉堆的元素: 3 3 5 4 5 6 8 5 4 删除最小元素：3二叉堆的元素: 3 4 5 4 5 6 8 5 删除最小元素：3二叉堆的元素: 4 4 5 5 5 6 8 删除最小元素：4二叉堆的元素: 4 5 5 8 5 6 删除最小元素：4二叉堆的元素: 5 5 5 8 6 删除最小元素：5二叉堆的元素: 5 6 5 8 删除最小元素：5二叉堆的元素: 5 6 8 删除最小元素：5二叉堆的元素: 6 8 删除最小元素：6二叉堆的元素: 8 删除最小元素：8二叉堆的元素: binaryHeap is empty.删除最小元素：0二叉堆的元素: binaryHeap is empty.删除最小元素：0二叉堆的元素: