我正在實施「Heapify」算法嗎？

Question

我正在爲計算機科學類創建一個堆實現，並且我想知道下面的遞歸函數是否會從不是堆的數組對象中創建堆。 的代碼如下：

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); 
    } 
} 

的想法是，你看，如果給定的索引數據是大於它的所有孩子。如果是這樣，該功能不會結束。否則，它檢查哪些是最大的（左邊或右邊的孩子），然後用索引交換。然後在交換髮生的索引處調用heapify。

通過ildjarn的要求，我包括我的完整的類定義和實現文件在我的問題的回答，以幫助：
這裏的頭文件：

#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 

和實現文件：

#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]; 
    } 
} 

Answer 1

您的算法有效。問題在於算法到代碼的轉換。假設你聲明的數據爲：

int Data[7]; 

和你的初始值{0, 1, 2, 3, 4, 5, 6}填充它。假設的LeftChild(i)和RightChild(i)的定義是這樣的：

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

那麼你的功能BuildHeap()，這應該是這樣的：

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); 
} 

將開始在右下角最子的Heapify過程樹根。在這種情況下，這是數組索引2，左邊的孩子是5，右邊的孩子是6. Heapify將正確交換2和6並遞歸調用Heapify(6)。

在這裏，整個事情可能擱淺！目前你的樹看起來像：

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

因此呼叫Heapify(6)會忠實地用Data[13]和Data[14]（C++和缺乏數組邊界執法，Java不同的危險）比較Data[6]值。顯然，後兩個值可以是RAM中剩下的任何垃圾。這裏的一個解決方案很醜，但是一個工作補丁，是在Data的聲明中添加8個元素，並將它們全部初始化爲比數組中任何元素都要低的值。更好的解決方案是將heapSize變量添加到您的類並設置它等於你的數組的長度：

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

邏輯然後集成到僅對比子節點，如果他們是樹的葉子有效。一個高效的執行是這樣的：

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); 
    } 
} 

所以總結一下，該解決方案是添加邏輯，以確保孩子節點是樹的有效樹葉，你的主要功能有類似也很簡單：

Heap heap; 

// initialize Data here  

heap.BuildHeap(); 

希望有所幫助。

Answer 2

你的代碼寫在這裏肯定感覺正確;但沒有什麼比寫幾個測試用例來看它如何執行。一定要用1，2，3，4和幾十個元素對堆進行測試。 （我預計基本情況是這塊不足的地方 - 當i沒有孩子時它會如何處理？對小堆的測試應該顯得匆忙。）

這件作品的一些小建議：

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 
} 

你也許可以通過在if塊僅設置指數獲得一定的可讀性：

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

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

Answer 3

號在樹上

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

輸出將是

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

其中有幾個堆違法行爲。 （我假設Data[l]和Data[r]是，如果不存在相應的兒童負無窮大。你可能需要額外的邏輯來確保這一點。）

你的函數的作用是修復的樹木，可能不是一個堆，但其左側和右側的子樹是堆。你需要在每個節點上以後序的方式調用它（也就是說，從n - 1到i的i），這樣當Heapify（i）被調用時，我的孩子就會堆積如山。

Answer 4

您的代碼現在成功構建了一個堆。只有一個概念上的缺陷：其餘的是逐個索引錯誤。在一個根本性的錯誤是BuildHeap：你有

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

，而這應該是

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

這是非常重要的，你必須看到，Heapify總是叫上一個樹根，以及（這是非常酷），您可以輕鬆找到索引（（heapSize/2）-1）處數組中最後一個樹根（這適用於C++和Java風格，其中第一個索引== 0）。它在代碼樹的最後葉上寫入名爲Heapify的代碼的方式是錯誤的。

除此之外，我添加了評論來標記錯誤的錯誤。我把它們放在左邊，這樣你可以很容易地找到它們。希望你對算法和數據結構有一個超級理解！ :-)

你的頭文件：

#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 

您的CPP文件：

#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; 
}