3

我正在学习堆，我发现了两种从给定数组构建它们的方法：我正在尝试构建一个 MAX 堆。

1.自上而下的方法

在这里，我只是检查每个元素是否在正确的位置。通过使用一种称为 restoreUp 的方法，其中每个键都与其父键进行比较，如果父键小于父键，则向下移动。此过程继续进行，直到父键更大。我检查每个键开始在索引位置 2。

我的代码是：

void restoreUp(int arr[],int i)
{
    int k=arr[i];
    int par=i/2;
    while(arr[par]<k)
    {
        arr[i]=arr[par];
        i=par;
        par=i/2;
    }
    arr[i]=k;
}
void buildheap1(int arr[],int size)
{
    int i;
    for(i=2;i<=size;i++)
       restoreUp(arr,i);
}
  1. 自下而上的方法

在这里，我从索引层（大小/2）处存在的第一个非叶节点开始，并调用方法 restoreDown 直到节点号 1。我将一个键与其左右子节点进行比较，然后将较大的子节点向上移动。如果两个孩子都大于钥匙，然后将两个孩子中较大的一个向上移动。当两个孩子都小于钥匙时，此过程停止。

我的代码是：

void restoreDown(int arr[],int i,int size)
{
    int left=2*i;
    int right=2*i+1;
    int num=arr[i];
    while(right<=size)
    {
        if(num>arr[left] && num>arr[right])
        {
            arr[i]=num;
            return;
        }
        else if(arr[left]>arr[right])
        {
            arr[i]=arr[left];
            i=left;
        }
        else
        {
            arr[i]=arr[right];
            i=right;
        }
        left=2*i;
        right=2*i+1;
    }
    if(left==size && arr[left]>num)
    {
        arr[i]=arr[left];
        i=left;
    }
    arr[i]=num;
}
void buildheap2(int arr[],int size)
{
    int i;
    for(i=size/2;i>=1;i--)
       restoreDown(arr,i,size);
}

这两种方法都对我有用。我只是想知道哪种方法更有效，为什么？

4

1 回答 1

0

一般来说，使用现代 CPU（具有缓存）。向后读取和数组通常是一个非常糟糕的主意，因为它会产生很多缓存未命中。除非（当然）数组已经在缓存中。

所以从这个角度来看，第一种方法似乎更好。

于 2013-07-23T06:48:15.787 回答