2011-11-15 41 views
16

Tôi đang tạo một triển khai heap cho một lớp khoa học máy tính, và tôi đã tự hỏi nếu hàm đệ quy sau đây sẽ tạo ra một đống từ một đối tượng mảng không phải là một đống. mã như sau:Tôi có đang triển khai thuật toán "Heapify" một cách chính xác không?

void Heap::Heapify(int i) 
{ 
    int temp, l, r, heapify; 
    l = LeftChild(i);// get the left child 
    r = RightChild(i);// get the right child 

    //if one of the children is bigger than the index 
    if((Data[i] < Data[l]) || (Data[i]< Data[r])) 
    { 
     //if left is the bigger child 
     if(Data[l] > Data[r]) 
     { 
      //swap parent with left child 
      temp = Data[i]; 
      Data[i] = Data[l]; 
      Data[l] = temp; 
      heapify = l; // index that was swapped 
     } 
     //if right is the bigger child 
     else 
     { 
      //swap parent with right child 
      temp = Data[i]; 
      Data[i] = Data[r]; 
      Data[r] = temp; 
      heapify = r; // index that was swapped 
     } 
     // do a recursive call with the index 
     //that was swapped 
     Heapify(heapify); 
    } 
} 

ý tưởng là bạn xem nếu dữ liệu ở các chỉ số nhất định là lớn hơn tất cả đó là trẻ em. Nếu có, hàm sẽ kết thúc không có vấn đề gì. Nếu không, nó kiểm tra xem cái nào là lớn nhất (trẻ em trái hoặc phải), và sau đó hoán đổi nó với chỉ mục. Các heapify sau đó được gọi là tại các chỉ số nơi trao đổi xảy ra.

theo yêu cầu ildjarn, tôi đang trong đó có đầy đủ định nghĩa lớp và thực hiện tác phẩm của tôi để hỗ trợ trong việc trả lời các câu hỏi của tôi:
đây là tập tin header:

#ifndef HEAP_H 
#define HEAP_H 
//Programmer: Christopher De Bow 
//Date: november 15, 2011 

class Heap 
{ 
private: 
    int Data [100]; 
    int Parent(int); 
    int RightChild(int); 
    int LeftChild(int); 
    void Heapify(int); 
    void BuildHeap(); 

public: 
    Heap(); 
    void insert(); 
    void HeapSort(); 
    void ExtractMaximum(); 
    int Maximum(); 
    void PrintHeap(); 
    int heapsize; 
    void SetData(int[]); 
}; 

#endif 

và tập tin thực hiện:

#include <iostream> 
#include "Heap.h" 
using namespace std; 
//Programmer: Christopher De Bow 
//Date: november 15, 2011 

Heap::Heap() 
{ 
    int init [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
    heapsize = 10; 
    SetData(init); 
} 

int Heap::Parent(int index) 
{ 
    int Rval; 
    if(index%2 == 0)// if the index is even 
    { 
     Rval = ((index-1)/2); 
    } 
    else// if the index is odd 
    { 
     Rval = (index/2); 
    } 
    return Rval; 
} 

int Heap::RightChild(int arrplace) 
{ 
    int ret; 
    ret = ((2*arrplace)+2); //rightchild is index times 2 plus 2 
    return ret; 
} 

int Heap::LeftChild(int i) 
{ 
    int rval; 
    rval = ((2*i)+1); //leftchild is index times 2 plus 1 
    return rval; 
} 

void Heap::Heapify(int i) 
{ 
    int temp, l, r, heapify; 

    l = LeftChild(i); // get the left child 
    r = RightChild(i); // get the right child 

    if((l <= heapSize) && (data[l] > data[i])) 
    { 
     heapify = l; 
    { 
    else 
    { 
     heapfiy = i; 
    } 
    if((r <= heapSize) && (data[r] > data[heapify])) 
    { 
     heapify = r; 
    } 
    if(heapify != i) // one of the two child nodes has proved 
    {    // larger than Data[i], so interchange values 
     //swap parent with left child 
     temp = Data[i]; 
     Data[i] = Data[heapify]; 
     Data[heapify] = temp; 
     Heapify(heapify); 
    } 
} 

void Heap::BuildHeap() 
{ 
    // we do not have a heap 
    // we will make a heap 
    // by calling heapify starting at the lowest 
    // internal node in the heap 
    for(int i = heapsize; i >= 1; i--) 
    { 
     Heapify(i-1); 
    } 
} 

void Heap::insert() 
{ 
    int insert; 
    heapsize = (heapsize + 1); 
    //getting data from the user 
    cout<<"what data would you like to insert?"<<endl; 
    cin>>insert; 
    Data[heapsize] = insert; 
    BuildHeap(); //call BuildHeap on array 
    cout<<"done"<<endl; 
} 

void Heap::PrintHeap() 
{ 
    BuildHeap(); 
    for(int count = 0; count < (heapsize-1); count++) 
    { 
     cout<<Data[count];// print out every element in heap 
    } 
    cout<<endl<<endl; 
} 

void Heap::HeapSort() 
{ 
    BuildHeap(); 
    int temp; 
    // do this for every elem in heap: 
    for(int i = 0; i < heapsize; i++) 
    { 
     temp = Data[heapsize-1]; 
     Data[heapsize-1] = Data[0]; 
     Data[0] = temp; 
     heapsize--; 
     BuildHeap(); 
    } 
    PrintHeap(); 
} 

void Heap::ExtractMaximum() 
{ 
    BuildHeap(); 
    //assign last thing in heap to first thing in heap 
    Data[0] = Data[heapsize]; 
    heapsize --; // decrease heapsize by one 
    Heapify(0); // heapify from the top 
} 

int Heap::Maximum() 
{ 
    int Rval; 
    BuildHeap();// make sure we have a heap 
    Rval = Data[0]; 
    return Rval; // return top thing 
} 

//initialize the elements in the "Data" array 
void Heap::SetData(int x[]) 
{ 
    for(int i = 0; i <= (heapsize); i++) 
    { 
     Data[i] = x[i]; 
    } 
} 
+19

Yay! Một câu hỏi bài tập về nhà với bằng chứng về nỗ lực!+1 – vcsjones

+1

D'aww, cảm ơn bạn rất nhiều! –

+0

@vcsjones: Thật vậy, đáng buồn là một sự hiếm có. – ildjarn

Trả lời

8

Thuật toán của bạn hoạt động. Vấn đề là trong bản dịch thuật toán mã. Giả sử bạn khai báo Dữ liệu là:

int Data[7]; 

và bạn điền nó với giá trị ban đầu {0, 1, 2, 3, 4, 5, 6}.Giả định nghĩa về LeftChild(i)RightChild(i) là một cái gì đó như:

#define LeftChild(i) ((i << 1) + 1) 
#define RightChild(i) ((i << 1) + 2) 

sau đó chức năng của bạn BuildHeap(), mà phải là một cái gì đó như:

void Heap::BuildHeap() 
{ 
    for(int i = (7 >> 1); i >= 1; i--) // in general, replace 7 with 
             // (sizeof(Data)/sizeof(int)), presuming 
             // you have an array of int's. if not, 
             // replace int with the relevant data type 
    Heapify(i-1); 
} 

sẽ bắt đầu quá trình Heapify trên bên phải thấp hơn hầu hết các tiểu gốc cây. Trong trường hợp này, đây là chỉ số mảng 2, có con trái là 5 và con phải là 6. Heapify sẽ trao đổi chính xác 2 và 6 và gọi đệ quy Heapify(6).

Tại đây, toàn bộ điều có thể bị mắc cạn! Hiện nay cây của bạn trông giống như:

      0 
        1   2 
       3  4 5  6 
      u n d e f i n e d s p a c e 

nên gọi Heapify(6) sẽ nghiêm túc so sánh các giá trị của Data[6] với Data[13]Data[14] (những nguy hiểm của C++ và thiếu thực thi ranh giới mảng, không giống như Java). Rõ ràng, hai giá trị sau có thể là bất kỳ thư rác nào còn lại trong RAM. Một giải pháp ở đây, xấu xí nhưng một bản vá hoạt động, là thêm 8 phần tử vào khai báo Dữ liệu và khởi tạo tất cả chúng với một số giá trị thấp hơn bất kỳ phần tử nào của mảng. Các giải pháp tốt hơn là thêm một biến heapSize đến lớp học của bạn và đặt nó bằng với chiều dài của mảng của bạn:

heapSize = (sizeof(Data)/sizeof(int)); 

Sau đó tích hợp logic để chỉ so sánh các nút con nếu họ là lá có giá trị của cây. An thực hiện hiệu quả của việc này là:

void Heap::Heapify(int i) 
{ 
    int temp, l, r, heapify; 

    l = LeftChild(i); // get the left child 
    r = RightChild(i); // get the right child 

    if((l <= heapSize) && (Data[l] > Data[i])) 
     heapify = l; 
    else heapfiy = i; 
    if((r <= heapSize) && (Data[r] > Data[heapify])) 
     heapify = r; 
    if(heapify != i) // one of the two child nodes has proved 
        // larger than Data[i], so interchange values 
    { 
     //swap parent with left child 
     temp = Data[i]; 
     Data[i] = Data[heapify]; 
     Data[heapify] = temp; 

     Heapify(heapify); 
    } 
} 

Vì vậy, để tóm tắt, giải pháp là đơn giản như thêm logic để đảm bảo các nút con là lá có giá trị của cây, và chức năng chính của bạn sẽ có cái gì đó như:

Heap heap; 

// initialize Data here  

heap.BuildHeap(); 

Hy vọng điều đó sẽ hữu ích.

1

Mã của bạn như được viết ở đây chắc chắn cảm thấy ngay; nhưng không có gì giống như viết một vài trường hợp thử nghiệm để xem nó hoạt động như thế nào. Hãy chắc chắn để kiểm tra với một đống với 1, 2, 3, 4, và hàng chục yếu tố. (Tôi mong đợi trường hợp cơ bản là nơi mảnh này rơi ngắn - làm thế nào nó xử lý khi i không có con ?. Thử nghiệm trên đống nhỏ nên thể hiện trong một vội vàng.)

Một số lời khuyên nhỏ cho đoạn này:

if(Data[l] > Data[r]) 
{ 
    //swap parent with left child 
    temp = Data[i]; 
    Data[i] = Data[l]; 
    Data[l] = temp; 
    heapify = l; // index that was swapped 
} 
//if right is the bigger child 
else 
    { //swap parent with right child 
    temp = Data[i]; 
    Data[i] = Data[r]; 
    Data[r] = temp; 
    heapify = r; // index that was swapped 
} 

Bạn có thể có thể đạt được một số mức độ dễ đọc bằng cách thiết lập chỉ index trong if khối:

if(Data[l] > Data[r]) { 
    swapme = l; 
} else { 
    swapme = r; 
} 

temp = Data[i]; 
Data[i] = Data[swapme]; 
Data[swapme] = temp; 
heapify = swapme; 
+0

Tôi đã chạy nó một vài lần, và nó sẽ không hoạt động. Nó hoàn toàn theo nghĩa đen không có gì để heap. Tuy nhiên tôi sử dụng một chức năng khác nhau để gọi nó từ, nhưng tất cả các chức năng đó là gọi nút nội bộ thấp nhất và sau đó gọi heapify từ đó. Tôi sẽ hỏi giáo sư của tôi vào ngày mai, nhưng tôi không hiểu @ _ @ –

+1

@Chris: Bạn có thể cập nhật câu hỏi của mình với định nghĩa lớp học đầy đủ không? Vấn đề có thể nằm ở nơi khác, ví dụ: trong ngữ nghĩa 'LeftChild' hoặc' RightChild', hoặc theo cách 'Dữ liệu' được khai báo. – ildjarn

8

số trên cây

 1 
    /\ 
    / \ 
/ \ 
    2  3 
/\ /\ 
6 7 4 5 

đầu ra sẽ là

 3 
    /\ 
    / \ 
/ \ 
    2  5 
/\ /\ 
6 7 4 1 

trong đó có nhiều vi phạm heap. (Tôi giả định rằng Data[l]Data[r] là trừ vô cùng nếu các con tương ứng không tồn tại. Bạn có thể cần thêm logic để đảm bảo điều này.)

Chức năng của bạn là sửa chữa một cái cây có thể không phải là đống mà trái và phải subtrees là đống. Bạn cần phải gọi nó trên mỗi nút, theo thứ tự (tức là, đối với i từ n - 1 xuống 0) sao cho con của tôi là đống khi Heapify (i) được gọi.

+1

bạn không cần phải gọi nếu cho các nút lá. –

4

Mã của bạn hiện đã tạo thành công một vùng heap. Chỉ có một lỗ hổng khái niệm: phần còn lại là các lỗi lập chỉ mục. Một trong những lỗi cơ bản là trong BuildHeap: bạn có

for(int i = heapSize; i >= 1; i--) 
{ 
    Heapify(i-1); 
} 

trong khi điều này nên được

for(int i = (heapSize/2); i >= 1; i--) 
{ 
    Heapify(i-1); 
} 

Điều này thực sự quan trọng, bạn phải thấy rằng Heapify luôn kêu gọi một gốc cây, và (đây là thực sự mát mẻ), bạn có thể dễ dàng tìm thấy gốc cây cuối cùng trong mảng tại chỉ mục ((heapSize/2) - 1) (điều này là dành cho kiểu C++ và Java, nơi chỉ mục đầu tiên == 0). Cách nó được viết mã của bạn được gọi là Heapify trên lá cuối cùng của cây, đó là do lỗi.

Khác hơn thế, tôi đã thêm nhận xét để gắn cờ các lỗi từng người một. Tôi đặt chúng tuôn ra bên trái để bạn có thể dễ dàng tìm thấy chúng. Hy vọng bạn sẽ hiểu được các thuật toán và cấu trúc dữ liệu của suberb! :-)

tập tin tiêu đề của bạn:

#ifndef HEAP_H 
#define HEAP_H 
//Programmer: Christopher De Bow 
//Date: november 15, 2011 

class Heap 
{ 
private: 
    int Data [100]; 
    int Parent(int); 
    int RightChild(int); 
    int LeftChild(int); 
    void Heapify(int); 
    void BuildHeap(); 
// SO added heapSize 
    int heapSize; 

public: 
    Heap(); 
    void insert(); 
    void HeapSort(); 
    void ExtractMaximum(); 
    int Maximum(); 
    void PrintHeap(); 
    int heapsize; 
    void SetData(int[]); 
}; 

#endif 

tập tin cpp của bạn:

#include <iostream> 
#include "Heap.h" 
using namespace std; 
//Programmer: Christopher De Bow 
//Date: november 15, 2011 

Heap::Heap() 
{ 
    int init [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
    heapSize = 10; 
    SetData(init); 
} 

int Heap::Parent(int index) 
{ 
    int Rval; 
    if(index%2 == 0)// if the index is even 
    { 
     Rval = ((index-1)/2); 
    } 
    else// if the index is odd 
    { 
     Rval = (index/2); 
    } 
    return Rval; 
} 

int Heap::RightChild(int arrplace) 
{ 
    int ret; 
    ret = ((2*arrplace)+2); //rightchild is index times 2 plus 2 
    return ret; 
} 

int Heap::LeftChild(int i) 
{ 
    int rval; 
    rval = ((2*i)+1); //leftchild is index times 2 plus 1 
    return rval; 
} 

void Heap::Heapify(int i) 
{ 
    int temp, l, r, heapify; 

    l = LeftChild(i); // get the left child 
    r = RightChild(i); // get the right child 

// you have to compare the index to (heapSize - 1) because we are working 
// with C++ and the first array index is 0 : l and r are direct indices 
// into the array, so the maximum possible index is the heapSize'th 
// element, which is at heapSize-1. this was kind of nasty as it let the 
// heapify index get too large and led to a swap with memory beyond the 
// last element of the array (again, C++ doesn't enforce array boundaries 
// as Java does). 
    if((l <= (heapSize-1)) && (Data[l] > Data[i])) 
     heapify = l; 
    else 
     heapify = i; 
// you have to compare the index to (heapSize - 1) because we are working 
// with C++ and the first array index is 0 : l and r are direct indices 
// into the array, so the maximum possible index is the heapSize'th 
// element, which is at heapSize-1. this was kind of nasty as it let the 
// heapify index get too large and led to a swap with memory beyond the 
// last element of the array (again, C++ doesn't enforce array boundaries 
// as Java does). 
    if((r <= (heapSize-1)) && (Data[r] > Data[heapify])) 
     heapify = r; 
    if(heapify != i) // one of the two child nodes has proved 
    {    // larger than Data[i], so interchange values 
     //swap parent with left child 
     temp = Data[i]; 
     Data[i] = Data[heapify]; 
     Data[heapify] = temp; 
     Heapify(heapify); 
    } 
} 

void Heap::BuildHeap() 
{ 
    // we do not have a heap 
    // we will make a heap 
    // by calling heapify starting at the lowest 
    // internal node in the heap 
// i must be initialized to (heapsize/2), please see my 
// post for an explanation 
    for(int i = heapSize/2; i >= 1; i--) 
    { 
     Heapify(i-1); 
    } 
} 

void Heap::insert() 
{ 
    int insert; 
    heapSize = (heapSize + 1); 
    //getting data from the user 
    cout<<"what data would you like to insert?"<<endl; 
    cin>>insert; 
    Data[heapSize] = insert; 
    BuildHeap(); //call BuildHeap on array 
    cout<<"done"<<endl; 
} 

void Heap::PrintHeap() 
{ 
    BuildHeap(); 
// the array indices are from 0 through (heapSize-1), so 
// count must be less than _or equal to_ (heapSize-1). another 
// way of phrasing this (which i applied in this function) 
// is (count < heapSize). you'll get better boundary conditions 
// with practice. 
    for(int count = 0; count < heapSize; count++) 
    { 
// added an endl to the output for clarity 
     cout << Data[count] << endl;// print out every element in heap 
    } 
    cout<<endl<<endl; 
} 

void Heap::HeapSort() 
{ 
    BuildHeap(); 
    int temp; 
    // do this for every elem in heap: 
    for(int i = 0; i < heapSize; i++) 
    { 
     temp = Data[heapSize-1]; 
     Data[heapSize-1] = Data[0]; 
     Data[0] = temp; 
     heapSize--; 
     BuildHeap(); 
    } 
    PrintHeap(); 
} 

void Heap::ExtractMaximum() 
{ 
    BuildHeap(); 
    //assign last thing in heap to first thing in heap 
    Data[0] = Data[heapSize]; 
    heapSize--; // decrease heapSize by one 
    Heapify(0); // heapify from the top 
} 

int Heap::Maximum() 
{ 
    int Rval; 
    BuildHeap();// make sure we have a heap 
    Rval = Data[0]; 
    return Rval; // return top thing 
} 

//initialize the elements in the "Data" array 
void Heap::SetData(int x[]) 
{ 
// the array indices are from 0 through (heapSize-1), so 
// count must be less than _or equal to_ (heapSize-1). another 
// way of phrasing this (which i applied in this function) 
// is (i < heapSize). you'll get better boundary conditions 
// with practice. 
    for(int i = 0; i < heapSize; i++) 
    { 
     Data[i] = x[i]; 
    } 
} 

// basic confirmation function 
int main() 
{ 
    Heap heap; 
    heap.PrintHeap(); 

    return 0; 
} 
Các vấn đề liên quan