我正确实施"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[6]with Data[13]和的值Data[14](与Java不同,C++的危险及其缺乏数组边界强制执行).显然,后两个值可以是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
 / \     / \
6   7   4   5

输出将是

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

它有几个堆违例.(我假设那个Data[l]并且Data[r]如果相应的孩子不存在则为负无穷大.你可能需要额外的逻辑来确保这一点.)

你的函数做的是修复一个树,它可能不是一堆,但其左右子树是堆.你需要在每个节点上调用它,后续顺序(即,对于i从n - 1下降到0),这样当调用Heapify(i)时,i的子节点就是堆.