heapSort发布java

Question

寻找一些简单的技巧来修复我的heapSort。希望这是一件简单的事情，我不明白。

我的dumpHeap()和extractMax()方法有问题。它似乎使dumpheap井然有序，但向我的数组中添加了一个0。从技术上讲，它仍然是一个堆，但是为什么会出现一个0，这让我很困扰。

我的另一个问题是，我的extractMax不会按降序提取最大数字，这会列出提取出来的数字。

我的输出读错了：

原阵列: 10 2 8 4 18 20 3 16 5

最高限额: 20 18 16 10 8 4 2 3 0 5

最多提取: 20 5 0 3 2 4 8 10 16

如果我能得到一些关于在哪里寻找/改变事物的建议，我们将不胜感激。

谢谢!

public class heap {

   public int size;
   public int [] H;
   public int position;

   public heap(int size)
   {
           this.size=size;
           H = new int [10];
           position = 0;
   }

   public void createHeap(int [] arrA)
   {
           if(arrA.length>0)
           {
                   for(int i=0;i<arrA.length;i++)
                   {
                          insert(arrA[i]);

                   }
           }        
    }

   public void dumpHeap()
   {
           for(int i=0;i<H.length;i++)
           {
                   System.out.print(" " + H[i]);            
           }
           System.out.println("");
   }

   public void insert(int x)
   {
           if(position==0)
           {
                      H[position]=x;
                      position = 2;
           }else{
                      H[position++]=x;
                      exchange();
                }
   }

  public void exchange()
  {
            int pos = position-1;
            while(pos > 0 && H[pos] > H[pos/2])
            {
                   int y = H[pos];
                   H[pos]=H[pos/2];
                   H[pos/2] = y;
                   pos = pos/2;
            }
  }

  public int extractMax()
  {
          int max = H[0];
          H[0]=H[position-1];
          H[position-1]= 0;
          position--;   
          extractSort(0);
          return max;
  }

  public void extractSort(int k)
  {
           int a = H[k];
           int maxNum =k;
           if(2*k>position && H[maxNum]<H[2*k])
           {
                    maxNum = 2*k;
           }

           if(2*k+1>position && H[maxNum]<H[2*k+1])
           {
                   maxNum = 2*k+1;
           }

           if(maxNum!=k)
           {
                      swap(maxNum,k);
                      extractSort(k);
           }

    }

    public void swap(int a, int b)
    {

             int temp = H[a];
             H[a] = H[b];
             H[b] = temp;
    }
}

public class heapMain {


     public static void main(String args[])
    {
           int arrA [] = {10,2,8,4,18,20,3,16,5};
           System.out.print("Original Array : ");
           for(int i=0;i<arrA.length;i++)
           {
                  System.out.print("  " + arrA[i]);
           }

           heap h = new heap(arrA.length);
           System.out.print("\nMax-Heap : ");
           h.createHeap(arrA);      
           h.dumpHeap();

           System.out.print("Extract Max :");
           for(int i=0;i<arrA.length;i++)
           {
                     System.out.print("  " + h.extractMax());
           }
     }
 }

Answer 1

我想你搞砸了数组的索引。

根据insert函数，您跳过索引1并将位置设置为2，这将使H[1]为0，这就是在dumpHeap()中看到0的原因。

如果您试图实现像这里这样的堆，则exchange()中的父索引选择算法有一些问题。索引1的父级为索引0，而索引2和3的父级为索引1。如果在所有方法中跳过索引0，此算法可能会很好，但似乎与它们混淆了。

第一，不要跳过insert()的索引1

public void insert(int x)
{
    H[position++] = x;
    exchange();
}

第二，正确计算父母和孩子的索引。

public void exchange()
{
  int pos = position-1;
  int parentPos = (pos-1)/2;
  while(pos > 0 && H[pos] > H[parentPos])
  {
     int y = H[pos];
     H[pos]=H[parentPos];
     H[parentPos] = y;
     pos = parentPos;
     parentPos = (pos-1)/2;
  }
}

第三，在extractSort()中使用正确的条件

  public void extractSort(int k)
  {
       int baseValue = H[k];
       int maxNumPos =k;
       int lhsPos = 2*k+1;
       int rhsPos = 2*k+2;
       if(lhsPos < position && H[maxNumPos] < H[lhsPos])
       {
           maxNumPos = lhsPos;
       }
       if(rhsPos < position && H[maxNumPos] < H[rhsPos])
       {
           maxNumPos = rhsPos;
       }

       if(maxNumPos!=k)
       {
                  swap(maxNumPos,k);
                  extractSort(maxNumPos);
       }
  }

输出可能是您想要的。

原阵列: 10 2 8 4 18 20 3 16 5 最高限额: 20 16 18 10 4 8 3 2 5 最多摘录: 20 18 16 10 8 5 4 3 2