چطور میشه در c++ ساختار heap رو ساخت ؟

Question

سلام توی c++ چه شکلی میشه heap رو ساخت و از heap sort استفاده کرد ؟

Answer 1

سلام به این شکل :

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

int main( )
{
    std::vector<int> vect={5,2,4,1,14,8,2};

    std::make_heap(vect.begin(),vect.end());

    for(auto& i:vect)
    {
        std::cout<<i<<" ";
    }
    std::cout<<"\n\nMax : "<<vect.front()<<"  Min : "<<vect.back()<<"\n\n";

    std::sort_heap(vect.begin(),vect.end());

    for(auto& i:vect)
    {
        std::cout<<i<<" ";
    }
}

 

Answer 2

با ساختار heap sort که اشنا هستید ؟؟

اول اعداد رو بگیرید و به ترتیب به اخر ارایه اضافه کنید بعد همونجا تا جایی که میشه رو درخت بیاریدش بالا بعد هم خونه اول ارایه میشه کوچکترین اون میخونید بعد اونو با خونه اخر ارایه swap میکنید و و تا جایی که میشه عدد رو ببرید پایین اگه توضیحات مفهموم نیست کد زیر رو ببینید : 

کد : 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN=100000+10;
int n,a[MAXN],siz;

void BubbleUp(int n)
{
    if(n/2 && a[n]<a[n/2])
    {
        swap(a[n],a[n/2]);
        BubbleUp(n/2);
    }
}
void BubbleDown(int n)
{
    if(2*n>siz)
        return;
    else if(2*n==siz)
    {
        if(a[2*n]<a[n])
        {
            swap(a[2*n],a[n]);
            BubbleDown(2*n);
        }
    }
    else
    {
        int x=2*n;
        if(a[2*n+1]<a[x])
            x++;
        if(a[n]>a[x])
        {
            swap(a[n],a[x]);
            BubbleDown(x);
        }
    }
}
int main()
{
    cin>>n; /// size of array
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        BubbleUp(i);
    }
    siz=n;
    for(int i=0;i<n;i++)
    {
        cout<<a[1]<<' ';
        swap(a[1],a[siz]);
        siz--;
        BubbleDown(1);
    }
    return 0;
}

 

اگه سوالی هست در خدمتم