Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Tạo heap từ mảng cho trước như thế nào?

  1. #1
    Ngày gia nhập
    03 2010
    Bài viết
    14

    Mặc định Tạo heap từ mảng cho trước như thế nào?

    Các bạn cho mình hỏi một chút, làm thế nào để tạo heap từ một mảng cho trước nhỉ?

  2. #2
    Ngày gia nhập
    09 2010
    Nơi ở
    thoát hiểm từ tộc Uchiha
    Bài viết
    9

    struct Node {
    int data;
    Node *next;}
    .....
    int i=0;
    Node*head=new Node();
    Node*temp=head;
    while(i<max) //max là giới hạn của mảng
    { temp->data=a[i];
    temp->next=NULL;
    i++;
    }
    ...
    Theo ý của mình là dùng linked List, mọi ngừoi có ý kiến j thì góp ý thêm nhe...

  3. #3
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    tại bước i xem như push(h[i])vào heap thôi
    C++ Code:
    1. #include<iostream>
    2. using namespace std;
    3. int h[1001];
    4. int nh,n;
    5. void up(int i)
    6. {
    7.      int j=i/2;
    8.      while (j&&h[j]>h[i])
    9.      {
    10.            swap(h[i],h[j]);
    11.            i=j;
    12.            j=i/2;
    13.      }
    14. }
    15. int pop()
    16. {
    17.     int k=h[1];
    18.     int r,c,v;
    19.     v=h[nh--];
    20.     r=1;
    21.     while (r*2<=nh)
    22.     {
    23.           c=r*2;
    24.           if (c<nh&&h[c+1]<h[c])c++;
    25.           if (h[c]>=v)break;
    26.           h[r]=h[c];
    27.           r=c;
    28.     }
    29.     h[r]=v;
    30.     return k;
    31. }
    32. int main()
    33. {
    34.     srand(time(NULL));
    35.     scanf ("%d",&n);
    36.     for (int i=1;i<=n;i++)
    37.     {
    38.         h[i]=rand()%100;
    39.         cout<<h[i]<<" ";
    40.         up(i);
    41.     }
    42.     nh=n;
    43.     cout<<endl;
    44.     while (nh)
    45.           cout<<pop()<<" ";
    46.     system("pause");
    47.     return 0;
    48. }

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  4. #4
    Ngày gia nhập
    03 2010
    Bài viết
    14

    Mình vẫn chưa hiểu code của các bạn lắm.

    Mình muốn tạo một heap như sau:
    Chẳng hạn có một mảng a[] = {1, 2, 5, 8, 9, 10};
    Thì nếu tại một node có key la a[i] thì left child của nó có key là a[2*i], right child của nó có key la a[2*i + 1].

  5. #5
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Bạn có trước mảng a[], mỗi bước bạn push(a[i]) vào heap, thay vì vậy mỗi bước bạn xem a[] là heap có i phần tử

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Mặc định Tạo heap từ mảng cho trước như thế nào?

    Cấu trúc heap tuy đơn giản nhưng rất hay. Cài heap bằng mảng rất dễ, hiểu thuật toán là cài được.
    Chẳng hạn có một mảng a[] = {1, 2, 5, 8, 9, 10};
    Thì nếu tại một node có key la a[i] thì left child của nó có key là a[2*i], right child của nó có key la a[2*i + 1].
    -> Nếu maxheap thì tìm thằng lớn hơn -> swap nó
    -> Nếu minheap thì tìm thằng nhỏ hơn -> swap nó
    Bạn cài thử đi, mình sẽ coi cho !

Các đề tài tương tự

  1. Thắc mắc về độ lớn vùng nhớ heap
    Gửi bởi practice1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 19-12-2011, 11:05 PM
  2. Lỗi heap corrupt khi dùng free trong C xử lý như thế nào?
    Gửi bởi anvachoi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 22
    Bài viết cuối: 06-05-2011, 10:51 PM
  3. Sự khác nhau của Heap Size và Array Length của mảng tạo thành Heap
    Gửi bởi cutithongtin trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 05-01-2011, 04:35 PM
  4. Thắc mắc: Số phần tử tối đa và tối thiểu của một (binary) heap!
    Gửi bởi clanks trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 22-12-2010, 08:26 PM
  5. Xử lý đa luồng? (Heap sỏt)
    Gửi bởi exdragonk trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 11
    Bài viết cuối: 28-09-2009, 11:18 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn