题解 | #字符串加解密#

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class MaxHeap{
public:

    MaxHeap(vector<int> vec, int k){
        data = new int[k];
        size = k;

        for(int i=0;i<k;i++)
            data[i]=0;

        for(int i=0;i<k;i++){
            data[i]=vec[i];
            shiftUp(i);
        }

        for(int i=k;i<vec.size();i++){
            if(vec[i]>data[0])
                continue;

            data[0]=vec[i];
            shiftDown(0);

        }

    }

    int extractMax(){
        int max=data[0];
        data[0]=data[size-1];
        shiftDown(0);
        size--;
        return max;
    }

    void printHeap(){
        vector<int> out;
        for(int i=0;i<size;i++)
            out.push_back(data[i]);

        sort(out.begin(),out.end());

        for(int i=0;i<out.size();i++)
            cout<<out[i]<<" ";
        cout<<endl;
    }

    ~MaxHeap(){
        delete [] data;
        data=nullptr;
    }

private:

    void shiftUp(int i){
        while(i>0 && data[i]>data[(i-1)/2]){
            swap(data[i],data[(i-1)/2]);
            i=(i-1)/2;
        }
    }

    void shiftDown(int i){
        while(2*i+1<size){
            int j=2*i+1;
            if(j+1<size && data[j+1]>data[j])
                j=j+1;

            if(data[i]>=data[j])
                break;

            swap(data[i],data[j]);
            i=j;

        }
    }

private:
    int * data;
    int size;
};

int main(){
    int n,k,temp;
    vector<int> input;
    while(cin>>n>>k){

        input.clear();
        while(n--){
            cin>>temp;
            input.push_back(temp);
        }

        MaxHeap heap(input,k);

        heap.printHeap();

    }

    return 0;
}