最短带权路径长度（哈夫曼树）
https://paste.ubuntu.com/p/RpTQvDPxcP/这是我的代码 本来以为已经解决这道题了 后来才发现我这样每次只考虑了3个数据假设权值有大量重复 比如 2 2 2 2 2 我跑出来的结果就是28而不是正确答案24 想请问一下有什么好的方法解决吗（不能使用其他头文件） #include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int Heap;//从1开始计数
int size=0; //heap size
void insert(int val) {
int i = ++size;
//please finish the following parts
while (i > 1 && val < Heap){ //finish this bracket
Heap = Heap;
i = i / 2;
}
Heap = val;
}
int delete_min() {
int val = Heap, ret = Heap;
int i = 1, ch = 2;
// please finish the following parts
while ( ch <= size){//finish this bracket
if(ch < size && Heap < Heap ) ch++;
if(val <= Heap) break;
Heap = Heap;
i = ch;
ch += ch;
}
Heap = val;
return ret;
}
int n, data1, data2, weight = 0;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{int temp;
cin>>temp;
insert(temp);}
for (int i = 0; i < n-1; i++) {
data1 = delete_min();
data2 = delete_min();
weight += data1 + data2;
insert(data1 + data2);
}
cout << weight ;
return 0;
}
页:
[1]