摘要：图，连通网，最小生成树，Prim算法， Java 实现Prim

一、相关概念

首先，我们得理解啥是最小生成树以及图的相关定义

• 连通图 ：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
• 强连通图 ：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图。
• 连通网 ：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树 ：一个 连通图 的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树 ：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

由上可知，最小生成树是对于连通网的，举个例子，如下所示：

我们知道，最小生成树的算法通常有两种： Kruskal算法 和 Prim算法 。这两种算法都是属于 贪心算法 。这篇博文研究的是Prim算法。

二、最小生成树的形成

怎么找到最小生成树呢，其实不管是 Kruskal算法 还是 Prim算法 都是一个原理： 找到一条轻量级边 ，举个简单例子，我们一个联通图的节点集合Q，和他的最小生成树A，那么树A中的节点与集合Q中的权重最小的边就为轻量级边，该轻量级边横跨了集合Q和树A，一定是属于最小生成树的，所以可以把该轻量级边在Q中的节点加入到最小生成树A中。具体原理以及证明请查看：算法导论第三版第六部分图算法最小生成树（625~628页）。因为篇幅原因，这里不做过多说明，总之Kruskal和Prim都是基于这个原理的。

三、Prim算法

Prim算法可以称为是“加点法”，不过本质上还是选择一条轻量级边，它具有的一个性质是集合A中的边总是构成一颗树。这棵树从一个任意的根节点r开始，一直长大到覆盖V中的所有节点位置。算法每一步在连接集合A和A之外的节点的所有边中，选择一条轻量级边加入到A中。本策略属于贪心策略，因为每一步所加入的边都必须是使树的总权重增加量最小的边。

算法 伪代码 如下：

 MST-PRIM(G,w,r)
    for each u <- G.V
        u.key=∞
        u.π =NIL
    r:key=0
    Q=G.V
    while Q≠O
        u=EXTRACT-MIN(Q)
        for each v <- G.Adj[u]
        if v<-Q and w(u,v)<v.key
           v.π=u
           v.key=w(u,v)
           DECREASE-KEY(Q,v)
        A=A∪{u}  

在上面的伪代码中，所有不在树A中的节点全部都存放在一个基于key属性的最小优先队列Q中，对于每个节点v， 属性v.key保存的是连接v和树中节点所有边中最小权重的边 ，我们约定若不存在这样子的边，则 u.key=∞ 。属性v.π给出的是节点v在树中的父节点。

举个例子

有如下连通网

根据上面的伪代码来运行

第一步：初始化A和优先队列Q

 A={},Q={A,B,C,D,E,F}
A.Key=0;A.π=Nil
B.Key=∞;B.π=Nil
C.Key=∞;C.π=Nil
D.Key=∞;D.π=Nil
E.Key=∞;E.π=Nil
F.Key=∞;F.π=Nil  

第二步：从Q中取出A来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A},Q={C,B,D,E,F}
A.key=0;A.π=NIL
B.key=6;B.π=A
C.key=1;C.π=A
D.key=5;D.π=A
E.key=∞;E.π=NIL
F.key=∞;F.π=NIL  

第三步：从Q中取出C来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A,C},Q={F,B,D,E}
A.key=0;A.π=NIL
C.key=1;C.π=A
B.key=5;B.π=C
D.key=5;D.π=A
E.key=6;E.π=C
F.key=4;F.π=C  

第四步：从Q中取出F来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A,C,F},Q={D,B,E}
A.key=0;A.π=NIL
C.key=1;C.π=A
F.key=4;F.π=C
B.key=5;B.π=C
D.key=2;D.π=F
E.key=6;E.π=C  

第五步：从Q中取出D来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A,C,F,D},Q={B,E}
A.key=0;A.π=NIL
C.key=1;C.π=A
F.key=4;F.π=C
D.key=2;D.π=F
B.key=5;B.π=C
E.key=6;E.π=C  

第七步：从Q中取出B来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A,C,F,D，B},Q={E}
A.key=0;A.π=NIL
C.key=1;C.π=A
F.key=4;F.π=C
D.key=2;D.π=F
B.key=5;B.π=C
E.key=3;E.π=B  

第八步：从Q中取出E来，更新各个节点到树A的距离，以及保证Q还是优先队列

 A={A,C,F,D,B,E},Q={}
A.key=0;A.π=NIL
C.key=1;C.π=A
F.key=4;F.π=C
D.key=2;D.π=F
B.key=5;B.π=C
E.key=3;E.π=B  

第九步：Q为空，结束。

由上面可以知道，根据伪代码中的逻辑，成功生产了图的最小生成树，我们现在聊分析下算法的复杂度！

四、Prim算法时间复杂度分析

我们现在来重新看一下Prim算法，把上面的伪代码拷贝下来

 MST-PRIM(G,w,r)
    for each u <- G.V
        u.key=∞
        u.π =NIL
    r:key=0
    Q=G.V
    while Q≠O
        u=EXTRACT-MIN(Q)
        for each v <- G.Adj[u]
        if v<-Q and w(u,v)<v.key
           v.π=u
           v.key=w(u,v)
           DECREASE-KEY(Q,v)
        A=A∪{u}  

算法的2~6行是建堆，我们知道最小优先队列的初始化时间成本为O(V）。因为有V个节点，所以while循环要执行V次，从最小优先队列中取出堆顶元素时间成本为O(lgV),所以第8行的总时间成本为O(VlgV)。因为邻接矩阵的边为2E，所以9~13行总执行次数为O(E)，在for循环里，我们可以在常数时间里完成对一个节点是否属于Q，方法就是对每个节点维护一个标志位来指明该节点是否属于Q，并在将节点从Q中删除的时候对该标志位进行更新。该算法12行因为改变了节点的key值，所以需要重新建堆，该操作在二叉最小堆上执行的时间成本为O(lgV)。因此第9~13行的总执行时间成本为O(ElgV)。所以Prim算法的总时间代价为O(V+VlgV+ElgV)=O(ElgV)。如果用斐波那契堆来实现最小优先队列Q，Prim算法的渐进运行时间可以进一步得到改善。

五、Java实现

我们这里用Java来实现Prim算法，根据上面的伪代码我们知道，我们需要实现一个最小优先队列，这里用最小堆来实现，代码如下：

 /**
 *最小堆实现的一个优先队列
* @author suibibk@qq.com
*/class PriorityQueue<E extends Comparable<E>> {
    //这里使用数组来实现
    private ArrayList<E> data;
    public PriorityQueue(int capacity) {
        data = new ArrayList<>(capacity);
    }
    public PriorityQueue() {
        data  = new ArrayList<>();
    }
    //返回堆中元素的个数
    public int getSize() {
        return data.size();
    }
    //返回二叉树中 索引 为index的节点的父节点索引
    public int parent(int index) {
        if(index == 0) {
            throw new IllegalArgumentException("index-0 dosen't have parent");
        }
        return (index-1)/2;
    }
    //返回完全二叉树中索引为index的节点的左孩子的索引
    private int leftChild(int index) {
        return index*2+1;
    }
    //返回完全二叉树中索引为index的节点的右孩子的索引
   private int rightChild(int index) {
       return index * 2 + 2;
   }
   //交换索引为i、j的值
   private void swap(int i, int j) {
       E t = data.get(i);
       data.set(i, data.get(j));
       data.set(j, t);
   }
   //向堆中添加元素
   public void add(E e) {
       data.add(e);
       siftUp(data.size() - 1);
   }
   //上浮
   private void siftUp(int k) {
       //k不能是根节点，并且k的值要比父节点的值小
       while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
           swap(k, parent(k));
           k = parent(k);
       }
   }
 //看堆中最小的元素
   public E findMin() {
       if (data.size() == 0)
           throw new IllegalArgumentException("Can not findMax when heap is empty");
       return data.get(0);
   }
   //取出堆中最小的元素
   public E extractMin() {
       E ret = findMin();
       swap(0, data.size() - 1);
       data.remove(data.size() - 1);
       siftDown(0);
       return ret;
   }
   /**
    * 当修改了堆中一些元素后,要执行先向下浮再向上浮的操作，这里需要重新建堆
    */   public void rebuildHead(E e) {
      // 这里优化为在建优先队列的时候，就指定节点在优先队列中的坐标，那么就不需要使用循环
       for (int j = 0; j < data.size(); j++) {
            if(e==data.get(j)) {
                siftDown(j);
                 siftUp(j);
                break;
            }
       }
   }
   //下浮
   private void siftDown(int k) {
       //leftChild存在
       while (leftChild(k) < data.size()) {
           int j = leftChild(k);
           //rightChild存在,且值小于leftChild的值
           if (j + 1 < data.size() &&
                   data.get(j).compareTo(data.get(j + 1)) > 0)
               j = rightChild(k);
           //data[j]是leftChild和rightChild中最小的
           if (data.get(k).compareTo(data.get(j)) <0)
               break;
           swap(k, j);
           k = j;
       }
   }
   //取出堆中最大的元素,替换为元素e
   public E replace(E e){
       E ret = findMin();
       data.set(0, e);
       siftDown(0);
       return ret;
   }
 //heapify操作:将数组转化为堆
  public PriorityQueue(E[] arrs) {
       data = new ArrayList<>(Arrays.asList(arrs));
       for (int i = parent(data.size() - 1); i >= 0; i--) {
           siftDown(i);
       }
   }
   public void print() {
       for (E e : data) {
            System.out.print(" "+e);
        }
   }
   public List<E> getDate() {
       return data;
   }
}  

该队列初始化的复杂度为O(V)，取出队头的复杂度为O(lgV),重新建堆的复杂度为O(lgV)，满足伪代码中的要求。

然后我们需要有一个节点对象，该对象不仅仅是当做图的节点，还要当做树A中的节点以及最小优先队列Q中的节点，所以不仅仅需要节点名称，还需要父节点，以及key属性，以及一个标志位表明是否存在Q中（这是为了让这个判定复杂度变为O(1)）。

//图的节点，当然也是最小优先队列Q的节点，也是最小生成树A的节点：因此多了属性key，parent，inQ

 //图的节点，当然也是最小优先队列Q的节点，也是最小生成树A的节点：因此多了属性key，parent，inQ
class Node implements Comparable<Node>{
    private int index;//坐标
    private int  key;//每个节点的key属性
    private String value;//节点名称
    private Node parent;//父节点
    private int inQ=1;//是否属于Q，默认是属于的，等离开才不属于
    @Override
    public int compareTo(Node o) {
        return this.key-o.key;
    }
    public Node(String value) {
        super();
        this.value = value;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public int getKey() {
        return key;
    }
    public void setKey(int key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
    public Node getParent() {
        return parent;
    }
    public void setParent(Node parent) {
        this.parent = parent;
    }
    public int getInQ() {
        return inQ;
    }
    public void setInQ(int inQ) {
        this.inQ = inQ;
    }
}  

然后我们需要一个图对象，可以方便的通过某一个节点找到相邻的节点，这里用的是邻接矩阵来存储图：

 //定义图：无向图
class Graph{
    //顶点数目
    int size;
    int index=0;
    //顶点
    private List<Node> vertexs;
    //边
    int[][] edges;
    //初始化
    public Graph(int size) {
        this.size=size;
        this.vertexs=new ArrayList<Node>(size);
        this.edges=new int[size][size];
    }
    //添加顶点
    public void addVertex(Node node) {
        node.setIndex(index);
        vertexs.add(node);
        index++;
    }
    //添加边:有权重有方向
    public void addEdge(Node vertex1,Node vertex2,int weight) {
        //因为是无向图，所以这里直接把两条边都加上
        edges[vertex1.getIndex()][vertex2.getIndex()]=weight;
        edges[vertex2.getIndex()][vertex1.getIndex()]=weight;
    }
    public List<Node> getVertexs() {
        return vertexs;
    }
    /***************上面已经做好了图，现在做遍历********************/    /**
     * 打印图
     * @param index
     */    public void printGraph() {
        System.out.print("图t ");
        for (Node vertex: vertexs) {
            System.out.print(vertex.getValue()+"t");
        }
        System.out.println("n");
        for (int i = 0; i <size; i++) {
            Node vertex = vertexs.get(i);
            System.out.print(vertex.getValue()+"t");
            for (int j = 0; j < size; j++) {
                System.out.print(edges[i][j]+"t");
            }
            System.out.println("n");
        }
        System.out.println();
    }
    /**
     * 获取节点index相邻的节点
     * @param index
     * @return
     */    public List<Node> getAdjacentVertexIndex(Node node) {
        List<Node> lists = new ArrayList<Node>();
        for (int j = 0; j < size; j++) {
            if(edges[node.getIndex()][j]!=0) {
                lists.add(vertexs.get(j));
            }
        }
        return lists;
    }
}  

上面都准备好了后，我们就可以根据伪代码中的逻辑来实现最小生成树啦！

 public static  List<Node> prim(Graph graph){
        //1、初始化一个最小优先队列
        PriorityQueue<Node> Q = new PriorityQueue<Node>();
        //这里第一个顶点的key是0，其他都是Integer.MAX_VALUE 代表无穷
        List<Node> nodes = graph.getVertexs();
        for (int i = 0; i < nodes.size(); i++) {
            Node node = nodes.get(i);
            node.setParent(null);
            if(i==0) {
                node.setKey(0);
            }else {
                node.setKey(Integer.MAX_VALUE);
            }
            Q.add(node);
        }
        //2、初始化生成树A，一开始树A为空，全部节点都还在Q中
        List<Node> A = new ArrayList<Node>();
        /**
         * 上面初始化最小堆的时间复杂度为O(V)
         */        //3、开始执行逻辑
        while(Q.getSize()!=0) {//这个要执行|V|次
            //4、获取第一个节点
            Node minNode = Q.extractMin();//这一步的时间复杂度是：O(VlgV)
            //5、取出这个节点对应的连接边
            List<Node> adjNodes = graph.getAdjacentVertexIndex(minNode);
            for (int i = 0; i < adjNodes.size(); i++) {//这里要执行|E|次
                //6、检查该节点是否属于集合Q
                Node node = adjNodes.get(i);
                /**
                 * 对每个节点维护一个标志位来指明该节点是否属于Q，
                 * 并在将节点Q从Q中移除的时候将标志位进行更新,时间复杂度则为O(1)
                 */                if(node.getInQ()==1) {
                    //7、获取这个邻接边的权重
                    int weight = graph.edges[minNode.getIndex()][node.getIndex()];
                    if(weight<node.getKey()) {
                        //8、更新node的值
                        node.setParent(minNode);
                        //这一行操作涉及后面需要重新建堆
                        node.setKey(weight);
                        //重新建堆
                        Q.rebuildHead(node);//这一步的时间复杂度是O(ElgV)
                    }
                }
            }
            //10，将该节点加入集合A
            minNode.setInQ(0);
            A.add(minNode);
        }
        //所以时间复杂度为O(V+VlgV+ElgV)=O(ElgV)=O(ElgV)
        return A;
    }  

好了，到这里就已经实现完了，把代码整合测试下：

Java实现Prim算法

 /**
 * 连通无向图最小生成树Prim算法Java实现
 * @author suibibk@qq.com
 */public class Prim {
    public static  List<Node> prim(Graph graph){
        //1、初始化一个最小优先队列
        PriorityQueue<Node> Q = new PriorityQueue<Node>();
        //这里第一个顶点的key是0，其他都是Integer.MAX_VALUE 代表无穷
        List<Node> nodes = graph.getVertexs();
        for (int i = 0; i < nodes.size(); i++) {
            Node node = nodes.get(i);
            node.setParent(null);
            if(i==0) {
                node.setKey(0);
            }else {
                node.setKey(Integer.MAX_VALUE);
            }
            Q.add(node);
        }
        //2、初始化生成树A，一开始树A为空，全部节点都还在Q中
        List<Node> A = new ArrayList<Node>();
        /**
         * 上面初始化最小堆的时间复杂度为O(V)
         */        //3、开始执行逻辑
        while(Q.getSize()!=0) {//这个要执行|V|次
            //4、获取第一个节点
            Node minNode = Q.extractMin();//这一步的时间复杂度是：O(VlgV)
            //5、取出这个节点对应的连接边
            List<Node> adjNodes = graph.getAdjacentVertexIndex(minNode);
            for (int i = 0; i < adjNodes.size(); i++) {//这里要执行|E|次
                //6、检查该节点是否属于集合Q
                Node node = adjNodes.get(i);
                /**
                 * 对每个节点维护一个标志位来指明该节点是否属于Q，
                 * 并在将节点Q从Q中移除的时候将标志位进行更新,时间复杂度则为O(1)
                 */                if(node.getInQ()==1) {
                    //7、获取这个邻接边的权重
                    int weight = graph.edges[minNode.getIndex()][node.getIndex()];
                    if(weight<node.getKey()) {
                        //8、更新node的值
                        node.setParent(minNode);
                        //这一行操作涉及后面需要重新建堆
                        node.setKey(weight);
                        //重新建堆
                        Q.rebuildHead(node);//这一步的时间复杂度是O(ElgV)
                    }
                }
            }
            //10，将该节点加入集合A
            minNode.setInQ(0);
            A.add(minNode);
        }
        //所以时间复杂度为O(V+VlgV+ElgV)=O(ElgV)=O(ElgV)
        return A;
    }
    /**
     * 打印最小生成树的节点A
     * @param graph 图 作用是找到节点名称
     * @param A
     */    public static void printPrim(List<Node> A) {
        //这里就已经生成了最小生成树了，遍历输出A
        for (int i = 0; i < A.size(); i++) {
            Node node = A.get(i);
            String vertex =  node.getValue();
            Node parent = node.getParent();
            String pVertex = "NIL";
            if(parent!=null) {
                pVertex=parent.getValue();
            }
            System.out.println("节点："+vertex+";父节点："+pVertex+";权重："+node.getKey());
        }
    }
    public static Graph getGraph() {
        Graph graph = new Graph(6);
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        graph.addVertex(A);
        graph.addVertex(B);
        graph.addVertex(C);
        graph.addVertex(D);
        graph.addVertex(E);
        graph.addVertex(F);
        graph.addEdge(A, B,6);
        graph.addEdge(A, D,5);
        graph.addEdge(A, C,1);
        graph.addEdge(B, C,5);
        graph.addEdge(C, D,5);
        graph.addEdge(B, E,3);
        graph.addEdge(D, F,2);
        graph.addEdge(C, F,4);
        graph.addEdge(E, F,6);
        graph.addEdge(E, C,6);
        return graph;
    }
    public static void main(String[] args) {
        //获取一个图
        Graph graph = getGraph();
        graph.printGraph();
        //获取该图的最小生成树
        List<Node> A = prim(graph);
        printPrim(A);
    }
}
//图的节点，当然也是最小优先队列Q的节点，也是最小生成树A的节点：因此多了属性key，parent，inQ
class Node implements Comparable<Node>{
    private int index;//坐标
    private int  key;//每个节点的key属性
    private String value;//节点名称
    private Node parent;//父节点
    private int inQ=1;//是否属于Q，默认是属于的，等离开才不属于
    @Override
    public int compareTo(Node o) {
        return this.key-o.key;
    }
    public Node(String value) {
        super();
        this.value = value;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public int getKey() {
        return key;
    }
    public void setKey(int key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
    public Node getParent() {
        return parent;
    }
    public void setParent(Node parent) {
        this.parent = parent;
    }
    public int getInQ() {
        return inQ;
    }
    public void setInQ(int inQ) {
        this.inQ = inQ;
    }
}
//定义图：无向图
class Graph{
    //顶点数目
    int size;
    int index=0;
    //顶点
    private List<Node> vertexs;
    //边
    int[][] edges;
    //初始化
    public Graph(int size) {
        this.size=size;
        this.vertexs=new ArrayList<Node>(size);
        this.edges=new int[size][size];
    }
    //添加顶点
    public void addVertex(Node node) {
        node.setIndex(index);
        vertexs.add(node);
        index++;
    }
    //添加边:有权重有方向
    public void addEdge(Node vertex1,Node vertex2,int weight) {
        //因为是无向图，所以这里直接把两条边都加上
        edges[vertex1.getIndex()][vertex2.getIndex()]=weight;
        edges[vertex2.getIndex()][vertex1.getIndex()]=weight;
    }
    public List<Node> getVertexs() {
        return vertexs;
    }
    /***************上面已经做好了图，现在做遍历********************/    /**
     * 打印图
     * @param index
     */    public void printGraph() {
        System.out.print("图t ");
        for (Node vertex: vertexs) {
            System.out.print(vertex.getValue()+"t");
        }
        System.out.println("n");
        for (int i = 0; i <size; i++) {
            Node vertex = vertexs.get(i);
            System.out.print(vertex.getValue()+"t");
            for (int j = 0; j < size; j++) {
                System.out.print(edges[i][j]+"t");
            }
            System.out.println("n");
        }
        System.out.println();
    }
    /**
     * 获取节点index相邻的节点
     * @param index
     * @return
     */    public List<Node> getAdjacentVertexIndex(Node node) {
        List<Node> lists = new ArrayList<Node>();
        for (int j = 0; j < size; j++) {
            if(edges[node.getIndex()][j]!=0) {
                lists.add(vertexs.get(j));
            }
        }
        return lists;
    }
}
/**
 *最小堆实现的一个优先队列
* @author suibibk@qq.com
*/class PriorityQueue<E extends Comparable<E>> {
    //这里使用数组来实现
    private ArrayList<E> data;
    public PriorityQueue(int capacity) {
        data = new ArrayList<>(capacity);
    }
    public PriorityQueue() {
        data  = new ArrayList<>();
    }
    //返回堆中元素的个数
    public int getSize() {
        return data.size();
    }
    //返回二叉树中索引为index的节点的父节点索引
    public int parent(int index) {
        if(index == 0) {
            throw new IllegalArgumentException("index-0 dosen't have parent");
        }
        return (index-1)/2;
    }
    //返回完全二叉树中索引为index的节点的左孩子的索引
    private int leftChild(int index) {
        return index*2+1;
    }
    //返回完全二叉树中索引为index的节点的右孩子的索引
   private int rightChild(int index) {
       return index * 2 + 2;
   }
   //交换索引为i、j的值
   private void swap(int i, int j) {
       E t = data.get(i);
       data.set(i, data.get(j));
       data.set(j, t);
   }
   //向堆中添加元素
   public void add(E e) {
       data.add(e);
       siftUp(data.size() - 1);
   }
   //上浮
   private void siftUp(int k) {
       //k不能是根节点，并且k的值要比父节点的值小
       while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
           swap(k, parent(k));
           k = parent(k);
       }
   }
 //看堆中最小的元素
   public E findMin() {
       if (data.size() == 0)
           throw new IllegalArgumentException("Can not findMax when heap is empty");
       return data.get(0);
   }
   //取出堆中最小的元素
   public E extractMin() {
       E ret = findMin();
       swap(0, data.size() - 1);
       data.remove(data.size() - 1);
       siftDown(0);
       return ret;
   }
   /**
    * 当修改了堆中一些元素后,要执行先向下浮再向上浮的操作，这里需要重新建堆
    */   public void rebuildHead(E e) {
      // 这里优化为在建优先队列的时候，就指定节点在优先队列中的坐标，那么就不需要使用循环
       for (int j = 0; j < data.size(); j++) {
            if(e==data.get(j)) {
                siftDown(j);
                 siftUp(j);
                break;
            }
       }
   }
   //下浮
   private void siftDown(int k) {
       //leftChild存在
       while (leftChild(k) < data.size()) {
           int j = leftChild(k);
           //rightChild存在,且值小于leftChild的值
           if (j + 1 < data.size() &&
                   data.get(j).compareTo(data.get(j + 1)) > 0)
               j = rightChild(k);
           //data[j]是leftChild和rightChild中最小的
           if (data.get(k).compareTo(data.get(j)) <0)
               break;
           swap(k, j);
           k = j;
       }
   }
   //取出堆中最大的元素,替换为元素e
   public E replace(E e){
       E ret = findMin();
       data.set(0, e);
       siftDown(0);
       return ret;
   }
 //heapify操作:将数组转化为堆
  public PriorityQueue(E[] arrs) {
       data = new ArrayList<>(Arrays.asList(arrs));
       for (int i = parent(data.size() - 1); i >= 0; i--) {
           siftDown(i);
       }
   }
   public void print() {
       for (E e : data) {
            System.out.print(" "+e);
        }
   }
   public List<E> getDate() {
       return data;
   }
}  

输入上面的图，运行结果如下：

可以看到结果跟伪代码执行逻辑结果是一样的，大功告成！要了老命，这篇笔记写了6个钟！