那几个角度在考虑的,全部极端出席集合后就获得所需的最小生成树365体育网址

   
 那篇我们看看第三种生成树的Kruskal算法,这么些算法的魅力在于大家得以打一下算法和数据结构的组合拳,很有意思的。

怎么着是最小生成树(MST)?

给定三个带权的无向连通图,选择一棵生成树(原图的不大连通子图),使生成树上全数边上权的总和为最小,称为该图的最小生成树。

求解最小生成树的算法一般有那三种:Prim算法和Kruskal算法。

一:思想

Prim算法(普Rim算法)

图的储备结构选用邻接矩阵。此格局是按梯次顶点连通的步骤举办,需求用二个终端集结,初始为空集,今后将以连片的终点陆续加入到聚聚焦,全体极限参预会集后就获得所需的最小生成树。

概括描述:

  1.初始化:Vnew =
{x},当中x为集合V中的任一节点(作为起头点),Enew = {},为空。

  2.在边会集E中精选权值最小的边<u,
v>,在那之中u为群集Vnew中的成分,而v不在Vnew聚拢个中,何况v∈V(如若存在有多条满意前述规范即全体一样权值的边,则可放肆选择当中之一)。将v加入集结Vnew中,将<u,
v>边参预会集Enew中。

  3.再一次操作2直至Vnew = V。

代码显示:

365体育网址 1365体育网址 2

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int INF=0x3f3f3f3f;
const int N=101;

int G[N][N];//邻接矩阵
int Lowest[N];//表示和已选顶点集Vnew的最小距离,Lowest[i]=0表示点i已经在Vnew中
int n,m;

int prim()
{
    int Num=0;//最小生成树权值

    for(int i=2;i<=n;i++)//选取第一个点开始
        Lowest[i]=G[1][i];//取第一行权值

    for(int i=1;i<n;i++)//找到新顶点加入(n-1个)
    {
        int minid=0;
        int mindis=INF;
        for(int j=2;j<=n;j++)//找到距离最小的
        {
            if(Lowest[j]!=0&&Lowest[j]<mindis)
            {
                mindis=Lowest[j];
                minid=j;
            }
        }
        Num+=mindis;
        Lowest[minid]=0;//把点minid加入Vnew

        for(int j=2;j<=n;j++)//更新Lowest数组
            if(Lowest[j]>G[minid][j])
                Lowest[j]=G[minid][j];
    }
    return Num;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(G,0x3f,sizeof(G));//初始化为最大值
        for(int i=1;i<=n;i++)//对角线为0
            G[i][i]=0;

        int u,v,w;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            G[u][v]=G[v][u]=w;
        }

        int MST=prim();//计算最小生成树总权值

        printf("%d\n",MST);
    }
}

View Code

   
若存在M={0,1,2,3,4,5}那样6个节点,大家驾驭Prim算法塑造生成树是从”顶点”那几个角度来构思的,然后利用“贪心理想”

Kruskal算法(克RussCarl算法

图的储备结构选用边集数组,且权值相等的边在数组中排列顺序能够是自由的。该措施对于边相对非常多的不是很实用,浪费时间。观念是贪心理想。

主意:将图中的边按其权值由小到大的顺序顺序选拔,若选边后不产生回路,则保留作为一条边,若酿成回路则除了这几个之外。依次选够(n-1)条边,即得最小生成树。(n为顶点数)

第一我们把具备的边依据权值先从小到大排列,接着依照顺序选拔每条边,借使那条边的七个端点不属于同一集结,那么就将它们统一,直到全体的点都属于同二个集结实现。至于怎么统一到一个凑合,那么这里大家就能够用到一个工具——-并查集(不知底的同窗请移步:Here)。换来说之,Kruskal算法正是依照并查集的利欲熏心算法。

代码突显:

365体育网址 3365体育网址 4

#include <cstdio>
#include <cstdlib>
#define MAXN 10010
using namespace std;

int Uset[MAXN];//并查集
int Rank[MAXN];//秩
typedef struct{
    int a, b, price;
}Node;
Node edge[MAXN];

int cmp(const void*a, const void *b){
    return ((Node*)a)->price - ((Node*)b)->price;
}

void Init(int n)//并查集初始化
{
    for(int i = 0; i < n; i++)
    {
        Rank[i] = 0;
        Uset[i] = i;
    }
}

int find(int x)
{
    int root = x;
    while(root != Uset[root]) root = Uset[root];
    while(x != root)
    {
        int t = Uset[x];
        Uset[x] = root;
        x = t;
    }
    return root;
}

void unionSet(int x, int y)
{
    x = find(x);
    y = find(y);
    if(Rank[x] > Rank[y])
        Uset[y] = x;
    else {
        Uset[x] = y;
        if(Rank[x] == Rank[y]) Rank[y]++;
    }
}

int Kruskal(int n, int m)
{
    int nEdge = 0, res = 0;

    qsort(edge, m, sizeof(edge[0]), cmp);//将边按照权值从小到大排序
    for(int i = 0; i < m && nEdge != n - 1; i++)
    {
        if(find(edge[i].a) != find(edge[i].b))//判断当前这条边的两个端点是否属于同一棵树
        {
            unionSet(edge[i].a, edge[i].b);
            res += edge[i].price;
            nEdge++;
        }
    }
    //如果加入边的数量小于m - 1,则表明该无向图不连通,等价于不存在最小生成树
    if(nEdge < n-1) res = -1;
    return res;
}
int main()
{
    int n, m, ans;//n为村庄的数量,m为边的数量
    while(scanf("%d%d", &n, &m)&&n)
    {
        Init(n);
        for(int i = 0; i < m; i++)
            scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].price);

        ans = Kruskal(n, m);
        if(ans == -1) printf("?\n");
        else printf("%d\n", ans);
    }
    return 0;
}

View Code

其余,能够参照:http://blog.csdn.net/luomingjun12315/article/details/47700237

365体育网址, 

作者: AlvinZH

出处: http://www.cnblogs.com/AlvinZH/

本人Github:https://github.com/Pacsiy/JobDu

正文版权归小编AlvinZH和博客园全部,款待转发和商用,但未经小编同意必得保留此段注明,且在篇章页面分明地方给出原版的书文连接,不然保留追究法律权利的权利。

来一步步扩展化,最终产生总体最优解,而Kruskal算法有一点点意思,它是站在”边“那个角度在图谋的,首先笔者有多个聚众。

  1. 极端集合(vertexs):

   
 比如M集结中的种种元素都足以以为是二个独根树(是还是不是想开了并查集?)。

2.边集合(edges):

    对图中的每条边依照权值大小进行排序。(是还是不是想到了优先队列?)

好了,上边该怎么操作呢?

率先:大家从edges中选出权值最小的一条边来作为生成树的一条边,然后将该边的七个终端合并为贰个新的树。

然后:大家继续从edges中选出次小的边作为生成树的第二条边,可是前提就是边的三个极点一定是属于多个集聚中,假如不是

        则剔除该边继续选下一条次小边。

末尾:经过三翻五次操作,当大家发掘n个顶点的图中生成树已经有n-1边的时候,此时生成树构建实现。

365体育网址 5

365体育网址 6

从图中我们依旧很驾驭的看到Kruskal算法营造生成树的事无巨细经过,同有时候大家也看到了”并查集“和“优先队列“那多个神器

来加速我们的生成树创设。

 

二:构建

1.Build方法

此间小编灌的是一些测验数据,同不常候在矩阵创设达成后,将顶点新闻纳入并查集,同一时间将边的音信归入事先队列,方便我们在

做生成树的时候秒杀。

 1 #region 矩阵的构建
 2         /// <summary>
 3         /// 矩阵的构建
 4         /// </summary>
 5         public void Build()
 6         {
 7             //顶点数
 8             graph.vertexsNum = 6;
 9 
10             //边数
11             graph.edgesNum = 8;
12 
13             graph.vertexs = new int[graph.vertexsNum];
14 
15             graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
16 
17             //构建二维数组
18             for (int i = 0; i < graph.vertexsNum; i++)
19             {
20                 //顶点
21                 graph.vertexs[i] = i;
22 
23                 for (int j = 0; j < graph.vertexsNum; j++)
24                 {
25                     graph.edges[i, j] = int.MaxValue;
26                 }
27             }
28 
29             graph.edges[0, 1] = graph.edges[1, 0] = 80;
30             graph.edges[0, 3] = graph.edges[3, 0] = 100;
31             graph.edges[0, 5] = graph.edges[5, 0] = 20;
32             graph.edges[1, 2] = graph.edges[2, 1] = 90;
33             graph.edges[2, 5] = graph.edges[5, 2] = 70;
34             graph.edges[4, 5] = graph.edges[5, 4] = 40;
35             graph.edges[3, 4] = graph.edges[4, 3] = 60;
36             graph.edges[2, 3] = graph.edges[3, 2] = 10;
37 
38             //优先队列,存放树中的边
39             queue = new PriorityQueue<Edge>();
40 
41             //并查集
42             set = new DisjointSet<int>(graph.vertexs);
43 
44             //将对角线读入到优先队列
45             for (int i = 0; i < graph.vertexsNum; i++)
46             {
47                 for (int j = i; j < graph.vertexsNum; j++)
48                 {
49                     //说明该边有权重
50                     if (graph.edges[i, j] != int.MaxValue)
51                     {
52                         queue.Eequeue(new Edge()
53                         {
54                             startEdge = i,
55                             endEdge = j,
56                             weight = graph.edges[i, j]
57                         }, graph.edges[i, j]);
58                     }
59                 }
60             }
61         }
62         #endregion

 

2:Kruskal算法

并查集,优先队列都有数据了,上面大家假设出队操作就行了,借使边的终点不在三个相会中,大家将其搜罗当做最小生成树的一条边,

按着那样的格局,最终生成树营造完成,如何,组合拳打客车爽不爽?

 1 #region Kruskal算法
 2         /// <summary>
 3         /// Kruskal算法
 4         /// </summary>
 5         public List<Edge> Kruskal()
 6         {
 7             //最后收集到的最小生成树的边
 8             List<Edge> list = new List<Edge>();
 9 
10             //循环队列
11             while (queue.Count() > 0)
12             {
13                 var edge = queue.Dequeue();
14 
15                 //如果该两点是同一个集合,则剔除该集合
16                 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))
17                     continue;
18 
19                 list.Add(edge.t);
20 
21                 //然后将startEdge 和 endEdge Union起来,表示一个集合
22                 set.Union(edge.t.startEdge, edge.t.endEdge);
23 
24                 //如果n个节点有n-1边的时候,此时生成树已经构建完毕,提前退出
25                 if (list.Count == graph.vertexsNum - 1)
26                     break;
27             }
28 
29             return list;
30         }
31         #endregion

聊到底是总的代码:

365体育网址 7365体育网址 8View
Code

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Diagnostics;
  6 using System.Threading;
  7 using System.IO;
  8 using System.Threading.Tasks;
  9 
 10 namespace ConsoleApplication2
 11 {
 12     public class Program
 13     {
 14         public static void Main()
 15         {
 16             MatrixGraph graph = new MatrixGraph();
 17 
 18             graph.Build();
 19 
 20             var edges = graph.Kruskal();
 21 
 22             foreach (var edge in edges)
 23             {
 24                 Console.WriteLine("({0},{1})({2})", edge.startEdge, edge.endEdge, edge.weight);
 25             }
 26 
 27             Console.Read();
 28         }
 29     }
 30 
 31     #region 定义矩阵节点
 32     /// <summary>
 33     /// 定义矩阵节点
 34     /// </summary>
 35     public class MatrixGraph
 36     {
 37         Graph graph = new Graph();
 38 
 39         PriorityQueue<Edge> queue;
 40 
 41         DisjointSet<int> set;
 42 
 43         public class Graph
 44         {
 45             /// <summary>
 46             /// 顶点信息
 47             /// </summary>
 48             public int[] vertexs;
 49 
 50             /// <summary>
 51             /// 边的条数
 52             /// </summary>
 53             public int[,] edges;
 54 
 55             /// <summary>
 56             /// 顶点个数
 57             /// </summary>
 58             public int vertexsNum;
 59 
 60             /// <summary>
 61             /// 边的个数
 62             /// </summary>
 63             public int edgesNum;
 64         }
 65 
 66         #region 矩阵的构建
 67         /// <summary>
 68         /// 矩阵的构建
 69         /// </summary>
 70         public void Build()
 71         {
 72             //顶点数
 73             graph.vertexsNum = 6;
 74 
 75             //边数
 76             graph.edgesNum = 8;
 77 
 78             graph.vertexs = new int[graph.vertexsNum];
 79 
 80             graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
 81 
 82             //构建二维数组
 83             for (int i = 0; i < graph.vertexsNum; i++)
 84             {
 85                 //顶点
 86                 graph.vertexs[i] = i;
 87 
 88                 for (int j = 0; j < graph.vertexsNum; j++)
 89                 {
 90                     graph.edges[i, j] = int.MaxValue;
 91                 }
 92             }
 93 
 94             graph.edges[0, 1] = graph.edges[1, 0] = 80;
 95             graph.edges[0, 3] = graph.edges[3, 0] = 100;
 96             graph.edges[0, 5] = graph.edges[5, 0] = 20;
 97             graph.edges[1, 2] = graph.edges[2, 1] = 90;
 98             graph.edges[2, 5] = graph.edges[5, 2] = 70;
 99             graph.edges[4, 5] = graph.edges[5, 4] = 40;
100             graph.edges[3, 4] = graph.edges[4, 3] = 60;
101             graph.edges[2, 3] = graph.edges[3, 2] = 10;
102 
103             //优先队列,存放树中的边
104             queue = new PriorityQueue<Edge>();
105 
106             //并查集
107             set = new DisjointSet<int>(graph.vertexs);
108 
109             //将对角线读入到优先队列
110             for (int i = 0; i < graph.vertexsNum; i++)
111             {
112                 for (int j = i; j < graph.vertexsNum; j++)
113                 {
114                     //说明该边有权重
115                     if (graph.edges[i, j] != int.MaxValue)
116                     {
117                         queue.Eequeue(new Edge()
118                         {
119                             startEdge = i,
120                             endEdge = j,
121                             weight = graph.edges[i, j]
122                         }, graph.edges[i, j]);
123                     }
124                 }
125             }
126         }
127         #endregion
128 
129         #region 边的信息
130         /// <summary>
131         /// 边的信息
132         /// </summary>
133         public class Edge
134         {
135             //开始边
136             public int startEdge;
137 
138             //结束边
139             public int endEdge;
140 
141             //权重
142             public int weight;
143         }
144         #endregion
145 
146         #region Kruskal算法
147         /// <summary>
148         /// Kruskal算法
149         /// </summary>
150         public List<Edge> Kruskal()
151         {
152             //最后收集到的最小生成树的边
153             List<Edge> list = new List<Edge>();
154 
155             //循环队列
156             while (queue.Count() > 0)
157             {
158                 var edge = queue.Dequeue();
159 
160                 //如果该两点是同一个集合,则剔除该集合
161                 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))
162                     continue;
163 
164                 list.Add(edge.t);
165 
166                 //然后将startEdge 和 endEdge Union起来,表示一个集合
167                 set.Union(edge.t.startEdge, edge.t.endEdge);
168 
169                 //如果n个节点有n-1边的时候,此时生成树已经构建完毕,提前退出
170                 if (list.Count == graph.vertexsNum - 1)
171                     break;
172             }
173 
174             return list;
175         }
176         #endregion
177     }
178     #endregion
179 }

并查集:

365体育网址 9365体育网址 10View
Code

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 
  6 namespace ConsoleApplication2
  7 {
  8     /// <summary>
  9     /// 并查集
 10     /// </summary>
 11     public class DisjointSet<T> where T : IComparable
 12     {
 13         #region 树节点
 14         /// <summary>
 15         /// 树节点
 16         /// </summary>
 17         public class Node
 18         {
 19             /// <summary>
 20             /// 父节点
 21             /// </summary>
 22             public T parent;
 23 
 24             /// <summary>
 25             /// 节点的秩
 26             /// </summary>
 27             public int rank;
 28         }
 29         #endregion
 30 
 31         Dictionary<T, Node> dic = new Dictionary<T, Node>();
 32 
 33         public DisjointSet(T[] c)
 34         {
 35             Init(c);
 36         }
 37 
 38         #region 做单一集合的初始化操作
 39         /// <summary>
 40         /// 做单一集合的初始化操作
 41         /// </summary>
 42         public void Init(T[] c)
 43         {
 44             //默认的不想交集合的父节点指向自己
 45             for (int i = 0; i < c.Length; i++)
 46             {
 47                 dic.Add(c[i], new Node()
 48                 {
 49                     parent = c[i],
 50                     rank = 0
 51                 });
 52             }
 53         }
 54         #endregion
 55 
 56         #region 判断两元素是否属于同一个集合
 57         /// <summary>
 58         /// 判断两元素是否属于同一个集合
 59         /// </summary>
 60         /// <param name="root1"></param>
 61         /// <param name="root2"></param>
 62         /// <returns></returns>
 63         public bool IsSameSet(T root1, T root2)
 64         {
 65             return Find(root1).CompareTo(Find(root2)) == 0;
 66         }
 67         #endregion
 68 
 69         #region  查找x所属的集合
 70         /// <summary>
 71         /// 查找x所属的集合
 72         /// </summary>
 73         /// <param name="x"></param>
 74         /// <returns></returns>
 75         public T Find(T x)
 76         {
 77             //如果相等,则说明已经到根节点了,返回根节点元素
 78             if (dic[x].parent.CompareTo(x) == 0)
 79                 return x;
 80 
 81             //路径压缩(回溯的时候赋值,最终的值就是上面返回的"x",也就是一条路径上全部被修改了)
 82             return dic[x].parent = Find(dic[x].parent);
 83         }
 84         #endregion
 85 
 86         #region 合并两个不相交集合
 87         /// <summary>
 88         /// 合并两个不相交集合
 89         /// </summary>
 90         /// <param name="root1"></param>
 91         /// <param name="root2"></param>
 92         /// <returns></returns>
 93         public void Union(T root1, T root2)
 94         {
 95             T x1 = Find(root1);
 96             T y1 = Find(root2);
 97 
 98             //如果根节点相同则说明是同一个集合
 99             if (x1.CompareTo(y1) == 0)
100                 return;
101 
102             //说明左集合的深度 < 右集合
103             if (dic[x1].rank < dic[y1].rank)
104             {
105                 //将左集合指向右集合
106                 dic[x1].parent = y1;
107             }
108             else
109             {
110                 //如果 秩 相等,则将 y1 并入到 x1 中,并将x1++
111                 if (dic[x1].rank == dic[y1].rank)
112                     dic[x1].rank++;
113 
114                 dic[y1].parent = x1;
115             }
116         }
117         #endregion
118     }
119 }

先行队列:

365体育网址 11365体育网址 12View
Code

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Diagnostics;
  6 using System.Threading;
  7 using System.IO;
  8 
  9 namespace ConsoleApplication2
 10 {
 11     public class PriorityQueue<T> where T : class
 12     {
 13         /// <summary>
 14         /// 定义一个数组来存放节点
 15         /// </summary>
 16         private List<HeapNode> nodeList = new List<HeapNode>();
 17 
 18         #region 堆节点定义
 19         /// <summary>
 20         /// 堆节点定义
 21         /// </summary>
 22         public class HeapNode
 23         {
 24             /// <summary>
 25             /// 实体数据
 26             /// </summary>
 27             public T t { get; set; }
 28 
 29             /// <summary>
 30             /// 优先级别 1-10个级别 (优先级别递增)
 31             /// </summary>
 32             public int level { get; set; }
 33 
 34             public HeapNode(T t, int level)
 35             {
 36                 this.t = t;
 37                 this.level = level;
 38             }
 39 
 40             public HeapNode() { }
 41         }
 42         #endregion
 43 
 44         #region  添加操作
 45         /// <summary>
 46         /// 添加操作
 47         /// </summary>
 48         public void Eequeue(T t, int level = 1)
 49         {
 50             //将当前节点追加到堆尾
 51             nodeList.Add(new HeapNode(t, level));
 52 
 53             //如果只有一个节点,则不需要进行筛操作
 54             if (nodeList.Count == 1)
 55                 return;
 56 
 57             //获取最后一个非叶子节点
 58             int parent = nodeList.Count / 2 - 1;
 59 
 60             //堆调整
 61             UpHeapAdjust(nodeList, parent);
 62         }
 63         #endregion
 64 
 65         #region 对堆进行上滤操作,使得满足堆性质
 66         /// <summary>
 67         /// 对堆进行上滤操作,使得满足堆性质
 68         /// </summary>
 69         /// <param name="nodeList"></param>
 70         /// <param name="index">非叶子节点的之后指针(这里要注意:我们
 71         /// 的筛操作时针对非叶节点的)
 72         /// </param>
 73         public void UpHeapAdjust(List<HeapNode> nodeList, int parent)
 74         {
 75             while (parent >= 0)
 76             {
 77                 //当前index节点的左孩子
 78                 var left = 2 * parent + 1;
 79 
 80                 //当前index节点的右孩子
 81                 var right = left + 1;
 82 
 83                 //parent子节点中最大的孩子节点,方便于parent进行比较
 84                 //默认为left节点
 85                 var min = left;
 86 
 87                 //判断当前节点是否有右孩子
 88                 if (right < nodeList.Count)
 89                 {
 90                     //判断parent要比较的最大子节点
 91                     min = nodeList[left].level < nodeList[right].level ? left : right;
 92                 }
 93 
 94                 //如果parent节点大于它的某个子节点的话,此时筛操作
 95                 if (nodeList[parent].level > nodeList[min].level)
 96                 {
 97                     //子节点和父节点进行交换操作
 98                     var temp = nodeList[parent];
 99                     nodeList[parent] = nodeList[min];
100                     nodeList[min] = temp;
101 
102                     //继续进行更上一层的过滤
103                     parent = (int)Math.Ceiling(parent / 2d) - 1;
104                 }
105                 else
106                 {
107                     break;
108                 }
109             }
110         }
111         #endregion
112 
113         #region 优先队列的出队操作
114         /// <summary>
115         /// 优先队列的出队操作
116         /// </summary>
117         /// <returns></returns>
118         public HeapNode Dequeue()
119         {
120             if (nodeList.Count == 0)
121                 return null;
122 
123             //出队列操作,弹出数据头元素
124             var pop = nodeList[0];
125 
126             //用尾元素填充头元素
127             nodeList[0] = nodeList[nodeList.Count - 1];
128 
129             //删除尾节点
130             nodeList.RemoveAt(nodeList.Count - 1);
131 
132             //然后从根节点下滤堆
133             DownHeapAdjust(nodeList, 0);
134 
135             return pop;
136         }
137         #endregion
138 
139         #region  对堆进行下滤操作,使得满足堆性质
140         /// <summary>
141         /// 对堆进行下滤操作,使得满足堆性质
142         /// </summary>
143         /// <param name="nodeList"></param>
144         /// <param name="index">非叶子节点的之后指针(这里要注意:我们
145         /// 的筛操作时针对非叶节点的)
146         /// </param>
147         public void DownHeapAdjust(List<HeapNode> nodeList, int parent)
148         {
149             while (2 * parent + 1 < nodeList.Count)
150             {
151                 //当前index节点的左孩子
152                 var left = 2 * parent + 1;
153 
154                 //当前index节点的右孩子
155                 var right = left + 1;
156 
157                 //parent子节点中最大的孩子节点,方便于parent进行比较
158                 //默认为left节点
159                 var min = left;
160 
161                 //判断当前节点是否有右孩子
162                 if (right < nodeList.Count)
163                 {
164                     //判断parent要比较的最大子节点
165                     min = nodeList[left].level < nodeList[right].level ? left : right;
166                 }
167 
168                 //如果parent节点小于它的某个子节点的话,此时筛操作
169                 if (nodeList[parent].level > nodeList[min].level)
170                 {
171                     //子节点和父节点进行交换操作
172                     var temp = nodeList[parent];
173                     nodeList[parent] = nodeList[min];
174                     nodeList[min] = temp;
175 
176                     //继续进行更下一层的过滤
177                     parent = min;
178                 }
179                 else
180                 {
181                     break;
182                 }
183             }
184         }
185         #endregion
186 
187         #region 获取元素并下降到指定的level级别
188         /// <summary>
189         /// 获取元素并下降到指定的level级别
190         /// </summary>
191         /// <returns></returns>
192         public HeapNode GetAndDownPriority(int level)
193         {
194             if (nodeList.Count == 0)
195                 return null;
196 
197             //获取头元素
198             var pop = nodeList[0];
199 
200             //设置指定优先级(如果为 MinValue 则为 -- 操作)
201             nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;
202 
203             //下滤堆
204             DownHeapAdjust(nodeList, 0);
205 
206             return nodeList[0];
207         }
208         #endregion
209 
210         #region 获取元素并下降优先级
211         /// <summary>
212         /// 获取元素并下降优先级
213         /// </summary>
214         /// <returns></returns>
215         public HeapNode GetAndDownPriority()
216         {
217             //下降一个优先级
218             return GetAndDownPriority(int.MinValue);
219         }
220         #endregion
221 
222         #region 返回当前优先队列中的元素个数
223         /// <summary>
224         /// 返回当前优先队列中的元素个数
225         /// </summary>
226         /// <returns></returns>
227         public int Count()
228         {
229             return nodeList.Count;
230         }
231         #endregion
232     }
233 }

 

相关文章