试题 基础练习 Huffuman树

试题 基础练习 Huffuman树

​ 翻了翻网上，基本都是暴力排序。我就提供一个最小堆的写法吧！

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

​ 点击这里，跳转查看最小堆插入删除函数的简单写法

Talk is cheap . Show me the code.

#include<iostream>
#include<algorithm>
#include<limits.h>
#include<vector>
using namespace std;
vector<int> minHeap;
void insert(int x) {
    minHeap.push_back(x);
    int child=minHeap.size()-1;
    while(minHeap[child/2]>minHeap[child]){
        swap(minHeap[child/2],minHeap[child]);
        child/=2;
    }
}
int Delete(){
    int value=minHeap[1];
    swap(minHeap[1],minHeap[minHeap.size()-1]);
    minHeap.pop_back();
    int parent=1,child=0;
    for(parent=1;parent*2<minHeap.size();parent=child){
        child=parent*2;
        if(child!=minHeap.size()-1&&minHeap[child+1]<minHeap[child]) child++;
        if(minHeap[parent]<minHeap[child]) break;
        else swap(minHeap[parent],minHeap[child]);
    }
    return value;
}
int main(){
    int n,temp=0;
    minHeap.push_back(INT_MIN);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>temp;
        insert(temp);
    }
    n=0;
    while(minHeap.size()>2){
        temp=Delete()+Delete();
        n+=temp;
        insert(temp);
    }
    cout<<n<<endl;
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄