365体育网址 这篇我们看看第三种生成树的Kruskal算法,对于一副

   
 这篇咱们看看第两种生成树的Kruskal算法,这个算法的魅力在于大家得以打一下算法和数据结构的组合拳,很有趣的。

一、定义

最小生成树(Minimum Spanning
Tree,MST)仅针对加权连通无向图。对于一副加权连通无向图,其生成树是它的一棵含有其独具终端的无环连通子图
最小生成树(MST)是指它的一棵权值最小的生成树。

365体育网址 1

1-1 最小生成树示例

API定义:

365体育网址 2

1-1 最小生成树的API定义

一:思想

二、性质

最小生成树的二种紧要算法(Prim算法和Kruskal算法)都基于切分定理
最小生成树具有以下性质:

  1. 具体V个顶点的加权连通无向图,其最小生成树包含V个顶点V-1条边
  2. 切分定理
    在一副加权连通无向图G中,将具有终端分成两个非空不相交子集U和V,假如顶点u∈U、v∈V,则对此权值最小的边e=(u,v),该图的最小生成树一定包含e。

证明(反证法):
如果T是图G的最小生成树,且T不含有e=(u,v)。
①依照树的概念,T中自然存在一条路径f(即使f≠e),连接U和V(因为树中存有终端必然是连接的);
②将e参加树T,p和e必然构成一个回路(树中参加任意一条边都会结合回路)
③去掉回路中比e大的边,将转变比原T权重更小的生成树T’(与原倘使中T是最小生成树冲突)

365体育网址 3

2-1 切分定理

   
若存在M={0,1,2,3,4,5}那样6个节点,大家了然Prim算法构建生成树是从”顶点”这么些角度来思考的,然后使用“贪心情想”

三、Prim算法实现

来一步步扩展化,最后形成完整最优解,而Kruskal算法有点意思,它是站在”边“这个角度在研究的,首先我有五个聚众。

3.1 基本考虑

Prim算法是为一棵生长中的树添加边,每回添加一条。
起来时,这棵树只有一个巅峰,然后添加V-1条边,每趟连续挑三拣四到树中随意顶点最短的边添加。
具体步骤:

  1. 将图中享有终端分属六个集合U和V:
    U:树顶点(已被选入生成树的巅峰)
    V:非树顶点(还未被选入生成树的顶峰)
  2. 拔取随机一个巅峰参预U
  3. 枚举U,找到U到V之间的一条最短路径,将这条最短路径对应的非树顶点插足树顶点。
  4. 重新步骤3(共V-1次),直到所有终端出席树顶点。

365体育网址 4

3-1 Prim算法示例

  1. 终端集合(vertexs):

3.2 源码实现

public class LazyPrimMST {
    private double weight;       // total weight of MST
    private Queue<Edge> mst;     // edges in the MST
    private boolean[] marked;    // marked[v] = true if v on tree
    private MinPQ<Edge> pq;      // edges with one endpoint in tree

    public LazyPrimMST(EdgeWeightedGraph G) {
        mst = new Queue<Edge>();
        pq = new MinPQ<Edge>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)     // run Prim from all vertices to
            if (!marked[v]) prim(G, v);     // get a minimum spanning forest
    }

    private void prim(EdgeWeightedGraph G, int s) {
        scan(G, s);
        while (!pq.isEmpty()) {                        // better to stop when mst has V-1 edges
            Edge e = pq.delMin();                      // smallest edge on pq
            int v = e.either(), w = e.other(v);        // two endpoints
            if (marked[v] && marked[w]) continue;      // lazy, both v and w already scanned
            mst.enqueue(e);                            // add e to MST
            weight += e.weight();
            if (!marked[v]) scan(G, v);               // v becomes part of tree
            if (!marked[w]) scan(G, w);               // w becomes part of tree
        }
    }

    // add all edges e incident to v onto pq if the other endpoint has not yet been scanned
    private void scan(EdgeWeightedGraph G, int v) {
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)]) pq.insert(e);
    }

    public Iterable<Edge> edges() {
        return mst;
    }
    public double weight() {
        return weight;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        LazyPrimMST mst = new LazyPrimMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }
}

   
 比如M集合中的每个元素都可以认为是一个独根树(是不是想开了并查集?)。

3.3 算法优化

3.2 中对的Prim算法能够选择目录优先队列优化:
目录优先队列保留各类非树顶点到树顶点集合的最短距离;一个distTo数组保存非树顶点v到树顶点集合的最短距离,伊始时为正无穷大。

365体育网址,优化版本源码:

public class PrimMST {
    // edgeTo保存最小生成树的边
    private Edge[] edgeTo;
    // distTo[v]表示非树顶点v到树顶点集合的最短距离,初始时为正无穷大
    private double[] distTo;
    private boolean[] marked;
    // 索引优先队列,保存各个非树顶点到树顶点集合的最短距离
    private IndexMinPQ<Double> pq;

    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMinPQ<Double>(G.V());
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        // run from each vertex to find minimum spanning forest
        for (int v = 0; v < G.V(); v++)
            if (!marked[v])
                prim(G, v);
    }

    // run Prim's algorithm in graph G, starting from vertex s
    private void prim(EdgeWeightedGraph G, int s) {
        distTo[s] = 0.0;
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) {
            int v = pq.delMin();    // 找到一条最短切边对应的顶点v
            marked[v] = true;       // 加入树顶点集合

            //对顶点v的邻边进行处理
            for (Edge e : G.adj(v)) {
                int w = e.other(v); 
                if (marked[w])
                    continue;
                if (e.weight() < distTo[w]) { // 更新w到树顶点集合的最短距离
                    distTo[w] = e.weight();
                    edgeTo[w] = e;
                    if (pq.contains(w))
                        pq.decreaseKey(w, distTo[w]);
                    else
                        pq.insert(w, distTo[w]);
                }
            }
        }
    }

    public Iterable<Edge> edges() {
        Queue<Edge> mst = new Queue<Edge>();
        for (int v = 0; v < edgeTo.length; v++) {
            Edge e = edgeTo[v];
            if (e != null) {
                mst.enqueue(e);
            }
        }
        return mst;
    }

    public double weight() {
        double weight = 0.0;
        for (Edge e : edges())
            weight += e.weight();
        return weight;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        PrimMST mst = new PrimMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }
}

2.边集合(edges):

3.4 性能分析

Prim算法的时刻复杂度一般为O(ElgV),拔取索引优先队列优化后得以直达O(ElgE)

    对图中的每条边遵照权值大小举办排序。(是不是想到了优先队列?)

四、Kruskal算法实现

好了,下面该怎么操作呢?

4.1 基本思维

Kruskal算法的主导步骤如下:

  1. 第一按边的权值从小到达排序;
  2. 每一次从剩余边中选出权值最小的,且顶点未联网的六个极端,插手到生成树中;
  3. 以至参预V-1条边结束。

365体育网址 5

4-1 Kruskal算法示意图

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

4.2 源码实现

public class KruskalMST {
    private static final double FLOATING_POINT_EPSILON = 1E-12;
    private double weight;                        // weight of MST
    private Queue<Edge> mst = new Queue<Edge>();  // edges in MST

    public KruskalMST(EdgeWeightedGraph G) {
        // more efficient to build heap by passing array of edges
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }
        // run greedy algorithm
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            if (!uf.connected(v, w)) { // v-w does not create a cycle
                uf.union(v, w);  // merge v and w components
                mst.enqueue(e);  // add edge e to mst
                weight += e.weight();
            }
        }
        // check optimality conditions
        assert check(G);
    }

    /**
     * Returns the edges in a minimum spanning tree (or forest).
     * @return the edges in a minimum spanning tree (or forest) as
     *    an iterable of edges
     */
    public Iterable<Edge> edges() {
        return mst;
    }

    /**
     * Returns the sum of the edge weights in a minimum spanning tree (or forest).
     * @return the sum of the edge weights in a minimum spanning tree (or forest)
     */
    public double weight() {
        return weight;
    }

    // check optimality conditions (takes time proportional to E V lg* V)
    private boolean check(EdgeWeightedGraph G) {
        // check total weight
        double total = 0.0;
        for (Edge e : edges()) {
            total += e.weight();
        }
        if (Math.abs(total - weight()) > FLOATING_POINT_EPSILON) {
            System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", total, weight());
            return false;
        }

        // check that it is acyclic
        UF uf = new UF(G.V());
        for (Edge e : edges()) {
            int v = e.either(), w = e.other(v);
            if (uf.connected(v, w)) {
                System.err.println("Not a forest");
                return false;
            }
            uf.union(v, w);
        }

        // check that it is a spanning forest
        for (Edge e : G.edges()) {
            int v = e.either(), w = e.other(v);
            if (!uf.connected(v, w)) {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

        // check that it is a minimal spanning forest (cut optimality conditions)
        for (Edge e : edges()) {
            // all edges in MST except e
            uf = new UF(G.V());
            for (Edge f : mst) {
                int x = f.either(), y = f.other(x);
                if (f != e) uf.union(x, y);
            }
            // check that e is min weight edge in crossing cut
            for (Edge f : G.edges()) {
                int x = f.either(), y = f.other(x);
                if (!uf.connected(x, y)) {
                    if (f.weight() < e.weight()) {
                        System.err.println("Edge " + f + " violates cut optimality conditions");
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * Unit tests the {@code KruskalMST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        KruskalMST mst = new KruskalMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }
}

然后:我们后续从edges中选出次小的边作为生成树的第二条边,但是前提就是边的四个极点一定是属于四个汇聚中,假使不是

4.3 性能分析

Kruskal算法一般依然比Prim算法慢,因为在处理每条边时,除了二种算法都要水到渠成的预先队列操作外,Kruskal算法还需要举行一遍并查集的connect()操作。

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

五、各样最小生成树算法的相比较

365体育网址 6

5-1 各种MST算法相比较

最后:经过一再操作,当我们发现n个顶点的图中生成树已经有n-1边的时候,此时生成树构建完毕。

365体育网址 7

365体育网址 8

从图中我们还是很明亮的看看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体育网址 9365体育网址 10View
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体育网址 11365体育网址 12View
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体育网址 13365体育网址 14View
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 }

 

相关文章