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