堆（优先级队列 PriorityQueue）

import java.io.*;
import java.util.*;
public class Main
{ 
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PriorityQueue<Integer> q = new PriorityQueue<Integer>();
    int n = in.nextInt();
    for (int i = 0; i < n; ++ i)
    {
      q.add(in.nextInt());
    }
    int sum = 0;
    while(q.size()>1)
    {
      int a = q.poll();
      int b = q.poll();
      sum += a + b;
      q.add(a + b);
    }
    System.out.println(sum);
  }
}

public static void main(String[] args) {
    PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>();     
    pqueue.add(100);
    pqueue.add(10);
    pqueue.add(11);
    pqueue.add(1);
    pqueue.add(646);
    System.out.println(pqueue);
    /*[1, 10, 11, 100, 646]*/
    for (Integer it : pqueue)
    {
      System.out.print(it + " ");
    }
    /*1 10 11 100 646 */
    System.out.println();
    Iterator<Integer> it = pqueue.iterator();
    while(it.hasNext())
    {
      System.out.print(it.next() + " ");
    }
    /*1 10 11 100 646 */
  }

public static void main(String[] args) {
    // 默认排序规则是升序排列
    // 可以自定义排序规则
    PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        int num = 0;
        if (o1 > o2) num = -1;
        else num = 1;
        return num;
      }
    });     
    pqueue.add(100);
    pqueue.add(10);
    pqueue.add(11);
    pqueue.add(1);
    pqueue.add(646);
    System.out.println(pqueue);
    /*[646, 100, 11, 1, 10]*/
  }