نمایش نتایج 1 تا 6 از 6

نام تاپیک: Max Heap

  1. #1

    Max Heap

    سلام
    من برنامه maxheap رو نوشتم ولی مشکل داره.کدش رو میزارم اگه کسی تونست کمک کنه ممنون می شم.
    کد:

    #include<iostream.h>
    #include<conio.h>
    void swap(int x,int y){
    int t;
    t=x;
    x=y;
    y=t;
    }
    class Heap
    {
    public:
    Heap(); //constructor
    void Make_Heap();
    void Make_MaxHeap();
    void Max_Heapfy(int);
    void Insert(int);
    void Remove(int);
    void Print();
    private:
    int table[100];
    int Heap_size;
    };
    Heap::Heap()
    {
    cout<<"Please Enter The Number of nodes:";
    cin>>Heap_size;
    cout<<"please enter The value of node:";
    for(int i=1;i<=Heap_size;i++)

    cin>>table[i];
    Make_MaxHeap();
    }
    //********************************
    void Heap::Make_MaxHeap()
    {
    for(int i=Heap_size/2;i>0;i--)
    Max_Heapfy(i);
    }
    //*********************************
    void Heap::Max_Heapfy(int i)
    {
    int L=2*i;
    int R=2*i+1;
    int largest=i;
    if(R<=Heap_size&&table[i]<table[R])
    largest=R;
    if(L<=Heap_size&&table[largest]<table[L])
    largest=L;
    if(largest!=i)
    {
    swap(table[i],table[largest]);
    Max_Heapfy(largest);
    }
    }
    //**********************************
    void Heap::Insert(int num)
    {
    Heap_size++;
    table[Heap_size]=num;
    for(int i=Heap_size/2;i>0;i--)
    Max_Heapfy(i);
    }
    //**********************************
    void Heap::Remove(int num)
    {
    int i,index;
    if(Heap_size>0)
    {
    for(i=1;i<=Heap_size;i++)
    if(table[i]==num)
    {
    index=i;
    break;
    }
    if(index!=Heap_size)
    {
    swap(table[index],table[Heap_size]);
    Heap_size--;
    for(i=Heap_size/2;i>0;i--)
    Max_Heapfy(i);
    }
    }
    }
    //*********************************
    void Heap::Print()
    {
    for(int i=1;i<=Heap_size;i++)
    cout<<table[i]<<' ';
    }
    //*********************************
    int main()
    {
    Heap H;
    int n,i;
    H.Make_MaxHeap();
    H.Print();
    cout<<"\n Enter A New Number:";
    cin>>n;
    H.Insert(n);
    H.Print();
    cout<<"Enter A number to remove it frome Heap:";
    cin>>n;
    H.Remove(n);
    H.Print();
    }
    آخرین ویرایش به وسیله whitehat : جمعه 26 بهمن 1386 در 21:51 عصر دلیل: اضافه کردن تگ کد

  2. #2
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495
    با عرض سلا م وخسته نباشی خدمت شما دوست عزیز.
    ببینید من برنامه شما رو دیدم ولی انگار شما مقصودتون رو از نوشتن یک maxHeap نمی دونید. maxHeap درختیه که از اون تو مرتب سازی از نوع HeapSort استفاده می کنند. بنابر این هنگام حذف یک عنصر تنها باید از ریشه حذف کرد و سپس دوباره درخت رو مرتب کرد (نه اینکه هر عنصر رو از هر کجا دلمون خواست حذف کنیم). من استراتژی شما رو تو متد max_heapfy دقیق متوجه نشدم ولی برای درج یک عنصر توی maxHeap ابتدا باید اون رو به آخرین عنصر آرایه اضافه کرد (برای اینکه ساختار درخت به صورت دودویی کامل بماند) و سپس درخت رو مرتب کرد. یعنی عنصر جدید به سمت جایگاه اصلی اش تو دخت به بالا حرکت می کنه و در صورت لزوم جاش رو با پدرش عوض می کنه . من این کار رو تو تابع عمل درج تو این درخت انجام دادم و برات نوشتم؛ امیدوارم بدردت بخوره.

    void maxHeapInsert(int nodes[], int n, int x)
    {
    int i = n+1; // n+1 is location in end of tree
    int j = i/2; // i div 2 ** j is index of i's parrent
    while((j>0) && (nodes[j]<x((
    // j>0 that is dosent arrive to root
    // nodes[j]<x that is x is larger than its parent
    }
    nodes[i] = nodes[j]; //replace parent in child
    i = j;
    j = i/2; // j is parent of i
    {

    nodes[i] = x; // i is right location of x
    {


    اگه خواستی الگوریتم حذفش هم برات می نویسم.
    آخرین ویرایش به وسیله whitehat : جمعه 26 بهمن 1386 در 21:54 عصر دلیل: اضافه کردن تگ کد

  3. #3
    بنابر این هنگام حذف یک عنصر تنها باید از ریشه حذف کرد و سپس دوباره درخت رو مرتب کرد (نه اینکه هر عنصر رو از هر کجا دلمون خواست حذف کنیم).
    چرا که نه؟ می تونیم از هر جای درخت حذف کنیم. فقط کافیه جای اون عضوی رو که قراره حذف بشه با عضو آخری heap عوض کنیم،‌سایر heap رو ۱ واحد کم کنیم، و بعد اون عنصر رو bubble-up یا bubble-down کنیم با توجه به این که max heap یا min heap داریم.

  4. #4
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495
    چرا که نه؟ می تونیم از هر جای درخت حذف کنیم.
    سلام آقای عدد. ممنون از راهنماییتون.
    ولی ممکنه بفرمایید فایده این کار چیه و کجا کاربرد داره؟

    با تشکر

  5. #5
    در جاهای بسیاری!!تعریف ش رو گفتم مثال که براش خیلییی زیاد هست

  6. #6

    نقل قول: Max Heap

    سلام میشه الگوریتم و کد حذفش رو هم بزارید؟

تاپیک های مشابه

  1. stack & heap
    نوشته شده توسط mohsenaminzare در بخش VB.NET
    پاسخ: 1
    آخرین پست: شنبه 20 بهمن 1386, 18:36 عصر
  2. Stack & Heap Memory
    نوشته شده توسط mr_esmaily در بخش برنامه نویسی با زبان C و ++C
    پاسخ: 2
    آخرین پست: چهارشنبه 22 تیر 1384, 10:22 صبح

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •