前段时间玩小爬虫的时候，我把url都是放在内存队列里面，有时我们在抓取url的时候，通过LCS之类的相似度比较，发现某些url是很重要的，需要后端解析服务器优先处理，针对这种优先级比较大的url，普通的队列还是苦逼的在做FIFO操作，现在我们的需求就是优先级大的优先服务，要做优先队列，非堆莫属。
一：堆结构1:性质堆是一种很松散的序结构树，只保存了父节点和孩子节点的大小关系，并不规定左右孩子的大小，不像排序树那样严格，又因为堆是一种完全二叉树，设节点为i,则i/2是i的父节点，2i是i的左孩子，2i+1是i的右孩子，所以在实现方式上可以采用轻量级的数组。
2：用途如果大家玩过微软的MSMQ的话，就会发现它其实也是一个优先队列，还有刚才说的抓取url，不过很遗憾，为什么.net类库中没有优先队列呢？而java1.5中就已经支持了。
3：实现1堆结构节点定义：我们在每个节点上定义一个level，表示该节点的优先级，也是构建堆时采取的依据。
///summary///定义一个数组来存放节点////summaryprivateListHeapNodenodeList=newListHeapNode();///summary///堆节点定义////summarypublicclassHeapNode{///summary///实体数据////summarypublicTt{get;set;}///summary///优先级别1-10个级别(优先级别递增)////summarypublicintlevel{get;set;}publicHeapNode(Tt,intlevel){this.t=t;this.level=level;}publicHeapNode(){}}2入队操作
入队操作时我们要注意几个问题：
①：完全二叉树的构建操作是“从上到下，从左到右”的形式，所以入队的节点是放在数组的最后，也就是树中叶子层的有序最右边空位。
②：当节点插入到最后时，有可能破坏了堆的性质，此时我们要进行“上滤操作”，当然时间复杂度为O(logN)。
当我将节点“20”插入到堆尾的时候，此时破坏了堆的性质，从图中我们可以清楚的看到节点“20”的整个上滤过程，有意思吧，还有一点就是：获取插入节点的父亲节点的算法是：parent=list.count/2-1。这也得益于完全二叉树的特性。
#region添加操作///summary///添加操作////summarypublicvoidEequeue(Tt,intlevel=1){//将当前节点追加到堆尾nodeList.Add(newHeapNode(t,level));//如果只有一个节点，则不需要进行筛操作if(nodeList.Count==1)return;//获取最后一个非叶子节点intparent=nodeList.Count/2-1;//堆调整UpHeapAdjust(nodeList,parent);}#endregion#region对堆进行上滤操作，使得满足堆性质///summary///对堆进行上滤操作，使得满足堆性质////summary///paramname="nodeList"/param///paramname="index"非叶子节点的之后指针（这里要注意：我们///的筛操作时针对非叶节点的）////parampublicvoidUpHeapAdjust(ListHeapNodenodeList,intparent){while(parent=0){//当前index节点的左孩子varleft=2*parent+1;//当前index节点的右孩子varright=left+1;//parent子节点中最大的孩子节点，方便于parent进行比较//默认为left节点varmax=left;//判断当前节点是否有右孩子if(rightnodeList.Count){//判断parent要比较的最大子节点max=nodeList[left].levelnodeList[right].level?right:left;}//如果parent节点小于它的某个子节点的话，此时筛操作if(nodeList[parent].levelnodeList[max].level){//子节点和父节点进行交换操作vartemp=nodeList[parent];nodeList[parent]=nodeList[max];nodeList[max]=temp;//继续进行更上一层的过滤parent=(int)Math.Ceiling(parent/2d)-1;}else{break;}}}#endregion3出队操作
从图中我们可以看出，优先级最大的节点会在一阵痉挛后上升到堆顶，出队操作时，我们采取的方案是：弹出堆顶元素，然后将叶子层中的最右子节点赋给堆顶，同样这时也会可能存在破坏堆的性质，最后我们要被迫进行下滤操作。
从图中可以看出：首先将堆顶20弹出，然后将7赋给堆顶，此时堆性质遭到破坏，最后我们清楚的看到节点7的下滤过程，从摊还分析的角度上来说，下滤的层数不超过2-3层，所以整体上来说出队的时间复杂度为一个常量O(1)。
#region优先队列的出队操作///summary///优先队列的出队操作////summary///returns/returnspublicHeapNodeDequeue(){if(nodeList.Count==0)returnnull;//出队列操作，弹出数据头元素varpop=nodeList[0];//用尾元素填充头元素nodeList[0]=nodeList[nodeList.Count-1];//删除尾节点nodeList.RemoveAt(nodeList.Count-1);//然后从根节点下滤堆DownHeapAdjust(nodeList,0);returnpop;}#endregion#region对堆进行下滤操作，使得满足堆性质///summary///对堆进行下滤操作，使得满足堆性质////summary///paramname="nodeList"/param///paramname="index"非叶子节点的之后指针（这里要注意：我们///的筛操作时针对非叶节点的）////parampublicvoidDownHeapAdjust(ListHeapNodenodeList,intparent){while(2*parent+1nodeList.Count){//当前index节点的左孩子varleft=2*parent+1;//当前index节点的右孩子varright=left+1;//parent子节点中最大的孩子节点，方便于parent进行比较//默认为left节点varmax=left;//判断当前节点是否有右孩子if(rightnodeList.Count){//判断parent要比较的最大子节点max=nodeList[left].levelnodeList[right].level?right:left;}//如果parent节点小于它的某个子节点的话，此时筛操作if(nodeList[parent].levelnodeList[max].level){//子节点和父节点进行交换操作vartemp=nodeList[parent];nodeList[parent]=nodeList[max];nodeList[max]=temp;//继续进行更下一层的过滤parent=max;}else{break;}}}#endregion
最后我还扩展了一个弹出并下降节点优先级的方法，好了，这个方法大家自己琢磨琢磨，很有意思的，实际应用中使用到了,下面是完整代码的网盘链接：
链接：