Notes

#include <iostream>
#include <queue>

using namespace std;

class MinHeap{
int mElements[50100];
int mSize;
void heapifyDown(int pos);
int heapifyUp();
public:
MinHeap();
void push(int value);
int top();
void pop();
};

MinHeap::MinHeap(){
//add a fake value to the head of heap
mElements[0] = -1;
mSize = 0;
}

void MinHeap::push(int value){
//upheap and downheap
//don't forget to downheap

mElements[++mSize] = value;

int upto = heapifyUp();
heapifyDown(upto);
}

int MinHeap::top(){
return mElements[1];
}

void MinHeap::pop(){
mElements[1] = mElements[mSize];
mSize--;
if (mSize > 0)
heapifyDown(1);
return;
}

int MinHeap::heapifyUp(){
int pos = mSize;
int val = mElements[mSize];
while (pos / 2 > 0 && mElements[pos] <= mElements[pos / 2]){
mElements[pos] = mElements[pos / 2];
pos /= 2;
}
mElements[pos] = val;
return pos;
}

void MinHeap::heapifyDown(int pos){
int val = mElements[pos];
while (pos * 2 <= mSize){
int child = pos * 2;
if (child < mSize && mElements[child + 1] < mElements[child])
++child;
if (val < mElements[child])
break;
mElements[pos] = mElements[child];
pos = child;
}
mElements[pos] = val;
}

int main()
{
int t, n;
cin >> t;
while (t-- > 0){
int x, a, b;
cin >> n;
MinHeap q;
for (int i = 0; i < n; i++){
cin >> x;
q.push(x);
}

long long res = 0;
for (int i = 0; i < n - 1; i++){
a = q.top(); q.pop();
b = q.top(); q.pop();
res = res + a + b;
q.push(a + b);
}
cout << res << endl;
}
}