0

我在考试中得到了这个问题，但我不确定我是否理解它要我做什么。如果我做了正确的事情，你能澄清一下吗？

问题

一个整数数组 A 被传递给函数makeHeap。如果 A[0] 包含 n，则 A[1] 到 A[n-1] 包含任意顺序的数字。写成makeHeapA[1] 到 A[n-1] 包含一个最小堆。您的函数必须通过按 A[2]、A[3]、...、A[n-1] 的顺序处理元素来创建堆。

我的解决方案

void makeHeap(int A[], int n)
{
  int r = n -1 ; 
  for(int i = 1; i <= n/2; i++)
    siftUp(a, i , r );
}

/* i- parent , r - right of the array */ 
void siftUp(int A[], int i , int r )
{
   boolean done = false ; 
   int j = 2* i ; 
   while (j <= r && !done)
   {
     if(A[j] > A[j+1]) // find the smalest child
       j+=1 ; 
     if(A[i] > A[j])
     {
       // code to swap A[i] and A[j]
       i = j ; 
       j = i*2 ;

     } 
     else done = true ; 
   }
}

这个解决方案甚至远程正确吗？另外，siftUp函数的名称是否正确？

编辑：

我的新解决方案

void makeHeap(int A[], int n)
{ 
  for(int i = 1; i <= A[0]/2; i++)
    siftUp(A, i );
}

/* i- parent */ 
void siftUp(int A[], int i )
{
   bool done = false ; 
   int j = 2* i ; 
   while (i > 1 && !done)
   {
     if(A[j] > A[j+1]) // find the smallest child
       j+=1 ; 
     if(A[i] > A[j])
     {
       /* swap A[j] and A[i] */
       int temp = A[i]; 
       A[i] = A[j]; 
       A[j] = temp ; 

       j = i ; 
       i = i / 2 ; 


     } 
     else done = true ; 
   }
}
4

1 回答 1

1

您的代码不会堆积数组（忽略和之类的a错误boolean）

对于 siftUp()，请记住属性parent(i) = i/2，其中i是节点的索引。将节点插入堆的一些伪代码（作为堆的最后一个节点）：

 Algo siftUp(H[], n)
     i = n
     while i > 1 and H[i] < H[i/2]
         swap(H[i], H[i/2])
         i = i / 2

当您遍历数组时，这将导致 O(nlogn)，但是使用 O(n) 的自下而上构造有更好的方法。

于 2017-04-25T06:34:00.573 回答