Huffman tree (optimal binary tree)

Huffman tree （ The best binary tree ）： The weighted path length of the tree is the smallest （ The weighted path of a tree refers to the step length from the root node to each leaf node * Sum of weights ）, Such a binary tree is a Huffman tree , Also called optimal binary tree .

Introduce a scenario ： take n Pile the fruits into a pile , Each pile consumes the physical strength of the same fruit quality , Ask how to pile these fruits , To minimize the consumption of physical strength , Such a problem is a Huffman tree , Its leaf node is the quality of the fruit （ It's like a pile of fruits at the end ）, A non leaf node is the sum of the masses of its child nodes , That is, the physical strength consumed , The root node is the sum of fruit quality , That is, the quality of the fruit pile , Because merging two fruits at a time consumes the mass of two fruit piles , So the last physical strength consumed is the sum of all non leaf nodes .

thus it can be seen , There is more than one binary tree in this scenario , Because the left and right children of the parent node of the leaf node can be exchanged , So there can be multiple Huffman trees , But the minimum weighted path of the tree must be unique , Because the construction of Huffman tree is the smallest two mergers , A little greedy algorithm , Minimize each step to achieve the minimum result .

Characteristics of Huffman tree ： There is no degree 1 The node of （ Degrees , The number of its child nodes ）, The higher the weight, the closer the node is to the root node .

Construct the Huffman tree ：

Ideas ： Repeatedly select the two smallest elements , Merge , Until there is only one element left , Use priority queues （ Namely heap structure ） To achieve
 

Example ：

Combine the fruits

　　 In an orchard , Dodo has beaten all the fruit down , And according to different kinds of fruits, they are divided into different heaps . Duoduo decides to combine all the fruits into a pile . Every merger , Duoduo can combine the two piles of fruit , The energy consumed is equal to the sum of the weight of two heaps of fruits . It can be seen that , All the fruits pass by n-1 After the merger , There's only one pile left . Duoduo's total energy consumed during fruit merging is equal to the sum of energy consumed during each merging .

　　 Because I have to work hard to carry these fruits home , Therefore, Duoduo should save energy as much as possible when merging fruits . Suppose that each fruit weighs 1, And we know the number of kinds of fruit and the number of each kind of fruit , Your task is to design a sequence plan for the merger , To minimize the amount of physical effort expended , And output this minimum energy cost .
　　 For example, there are 3 Plant fruit , The order of numbers is 1,2,9. You can put 1、2 Heap merge , The number of new piles is 3, Expend physical energy for 3. next , Merge the new pile with the original third pile , And get a new pile , The number is 12, Expend physical energy for 12.
So a lot of energy =3+12=15. Can prove that 15 For the minimum physical cost .

Input

　　 The input consists of two lines , The first line is an integer n(1<＝n<=10000), The number of kinds of fruit .
　　 The second line contains n It's an integer , Separate... With spaces , The first i It's an integer ai(1<＝ai<=20000) It's No i The number of fruits planted .

Output

　　 The output includes a line , This line contains only one integer , That's the minimum physical cost . Input data to ensure that the value is less than 2^31.

The sample input  Copy

3
1 2 9

Sample output  Copy

15

Code ：
 

// The establishment of Huffman tree ;
#include<iostream>
#include<queue> 
using namespace std;

priority_queue<long long , vector<long long >, greater<long long> > q;// Priority queue  
// Knowledge of priority queues ： Priority queues are implemented with heaps 
// Can pass greater In this way, priority setting is used to realize internal sorting ,long long  Is the element type in the queue ,vector<long long > Is the bottom of the priority queue heap Implemented container ; 
int main ( ){
	int n;
	long long temp, x, y,ans = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%lld", &temp);
		q.push(temp);
	}
	
	while(q.size() > 1) {// The establishment of Huffman tree , Two minimum values in the team are merged , Until there's only one element left ; 
		x = q.top( );//priority_queue Only use top Visit the team leader element with the highest priority , Out of commission front and back visit ;
		q.pop( );
		y = q.top( ); 
		q.pop( );
		q.push(x + y);// Merge ;
		ans += x + y;   
	}
	printf("%lld", ans);
	return 0;
}