给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树
也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
权值最小的两个点深度一定最深并且可以互为兄弟结点
每次都合并最小的两个点
使用堆来进行求解:
while ( n -- )
{
int x;
cin >> x;
heap.push(x);
}
int res = 0;
while ( heap.size() > 1)
{
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
res += a + b;
heap.push(a+b);
}