package algorithm.basic07;

import java.util.Comparator;

import java.util.PriorityQueue;

/**

* @author mood321

* @date 2019/11/11

* @email [email protected]

*/

public class Code_02_Less_Money {

public static int lessMoney(int[] arr) {

if(arr==null){

return 0;

}

PriorityQueue<Integer> minQueue = new PriorityQueue<>();

for (int i : arr) {

minQueue.add(i);

}

int sum=0;

int cur=0;

while(minQueue.size()>1){

cur = minQueue.poll() + minQueue.poll();

sum +=cur;

minQueue.add(cur);

}

return sum;

}

public static class MinheapComparator implements Comparator<Integer> {

@Override

public int compare(Integer o1, Integer o2) {

return o1 - o2; // < 0 o1 < o2 负数

}

}

public static class MaxheapComparator implements Comparator<Integer> {

@Override

public int compare(Integer o1, Integer o2) {

return o2 - o1; // < o2 < o1

}

}

public static void main(String[] args) {

// solution

int[] arr = { 6, 7, 8, 9 };

System.out.println(lessMoney(arr));

int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 };

// min heap

PriorityQueue<Integer> minQ1 = new PriorityQueue<>();

for (int i = 0; i < arrForHeap.length; i++) {

minQ1.add(arrForHeap[i]);

}

while (!minQ1.isEmpty()) {

System.out.print(minQ1.poll() + " ");

}

System.out.println();

// min heap use Comparator

PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinheapComparator());

for (int i = 0; i < arrForHeap.length; i++) {

minQ2.add(arrForHeap[i]);

}

while (!minQ2.isEmpty()) {

System.out.print(minQ2.poll() + " ");

}

System.out.println();

// max heap use Comparator

PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxheapComparator());

for (int i = 0; i < arrForHeap.length; i++) {

maxQ.add(arrForHeap[i]);

}

while (!maxQ.isEmpty()) {

System.out.print(maxQ.poll() + " ");

}

}

}