这篇文章主要介绍堆（最大堆和最小堆），以及一些系统对一些任务，比如线程，进程做调度的时候，所采用的优先级队列。
主要思想就是，做一个最大堆（任务的权重最大的在顶端），把顶端的任务取出，重新做一个堆，处理该任务。
// 优先级队列.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include <functional>
#include <iostream>
using namespace std;template<typename T , class FuncCmp = std::less<T> >
class priqueue
{T * x;int n;int maxsize;FuncCmp comp;
private:inline void swap(T & l , T & r){T tmp = l;l = r;r = tmp;}public:void shiftup(int end)//将满足comp的元素，从底部提到顶部{//pre : [1,n-1]是堆//post : [1,n]是堆int i = end;int p = i/2;while( i != 1 && comp(x[i],x[p]) ){swap(x[i],x[p]);i = p;p = i / 2;}}void shiftdown(int end)//将不满足comp的元素，从顶部往下移{//pre : [2,n]是堆//post : [1,n]是堆int i = 1;int child;while (1){child = 2*i;if (child > end)break;if(child == end){if ( !comp(x[i],x[child]) ){swap(x[i] , x[child]);}break;}if (child < end){if ( !comp(x[child],x[child+1]) ){++child;}if ( !comp(x[i],x[child]) ){swap(x[i],x[child]);}else{break;}}i = child;}}void push_queue(T t){if (n == maxsize)return;x[++n] = t;shiftup(n);}T pop_queue(){if(n == 0)return T();T ret = x[1];x[1] = x[n--];shiftdown(n);x[n+1] = ret;return ret;}void make_heap(){if(n == 0 || n==1)return;for (int i = 2;i<=n ; ++i){shiftup(i);}}priqueue(int m){maxsize = m;n = 0;x = new T[maxsize + 1];}~priqueue(){if (x){delete x;x = NULL;}}int size()const{return n;}
};struct Tasks
{int priority;struct OtherData{int data1;int data2;int data3;int data4;};
};inline bool CompareTasks(Tasks * t1 , Tasks * t2)
{return t1->priority < t2->priority;
}struct CompareTasksType
{
public:bool operator()(Tasks * t1 , Tasks * t2){return CompareTasks(t1,t2);}
};int _tmain(int argc, _TCHAR* argv[])
{priqueue<Tasks * , CompareTasksType> q(12);Tasks t1; t1.priority = 12;Tasks t2; t2.priority = 20;Tasks t3; t3.priority = 15;Tasks t4; t4.priority = 29;Tasks t5; t5.priority = 23;Tasks t6; t6.priority = 17;Tasks t7; t7.priority = 22;Tasks t8; t8.priority = 35;Tasks t9; t9.priority = 40;Tasks t10; t10.priority = 26;Tasks t11; t11.priority = 51;Tasks t12; t12.priority = 19;q.push_queue(&t1);q.push_queue(&t2);q.push_queue(&t3);q.push_queue(&t4);q.push_queue(&t5);q.push_queue(&t6);q.push_queue(&t7);q.push_queue(&t8);q.push_queue(&t9);q.push_queue(&t10);q.push_queue(&t11);q.push_queue(&t12);//q.push_queue(12);//q.push_queue(20);//q.push_queue(15);//q.push_queue(29);//q.push_queue(23);//q.push_queue(17);//q.push_queue(22);//q.push_queue(35);//q.push_queue(40);//q.push_queue(26);//q.push_queue(51);//q.push_queue(19);while(q.size() != 0){Tasks * pT = q.pop_queue();//do this task//...cout<<(pT->priority)<<endl;}return 0;
}