我在这里使用最小堆,但我做错了。我正在尝试按宽度顺序打印出一些绵羊,同时从最轻到最重进行排序

  • 本文关键字:打印 排序 顺序 在这里 错了 java heap min-heap
  • 更新时间 :
  • 英文 :


我的堆支持按宽度顺序打印出来,并从最轻到最重(最小堆)对绵羊进行排序。我的测试文件应该添加15只绵羊,并删除至少5只。我还没有尝试删除部分,因为我得到了一个数组索引越界错误。感谢您的帮助。

以下是我的课程:

public class Sheep {
    private double weight;
    private String name;
    public Sheep()
    {
        weight = 0.0;
        name = "null";
    }
    public Sheep(double aWeight, String aName)
    {
        this.weight = aWeight;
        this.name = aName;
    }
    public double getWeight() {
        return weight;
    }
    public void setWeight(double weight) {
        this.weight = weight;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }

    //may not be necessary...
    @Override
    public String toString() {
        return "Sheep [weight=" + weight + ", name=" + name + "]";
    }
    //this may not be necessary...
    public int compareTo(Sheep sheep)
    {
        if (this.weight>sheep.weight)
            return 1;
        else if(this.weight<sheep.weight)
            return -1;
        else
            return 0;
    }
}
//****************************************

public class SheepHeapMain {
    private Sheep[]heap;
    private static int size;
    private static final int FIRST=1; //possibly needed, how do you do this

    public SheepHeapMain()
    {
        heap = (Sheep[])(new Comparable[100]);
        size = 0;
    }
    public SheepHeapMain(int aSize)
    {
        heap = new Sheep[aSize];
    }
    public void addSheep(Sheep val)
    {
        if(size >= heap.length)
        {
            System.out.println("Max size of heap has been reached");
            return;
        }
        heap[size] = val;
        climbUp();
        size++;
    }
    public void climbUp()
    {
        int index = this.size;
        while(index>0 &&//It has a parent
                heap[index/2].compareTo(heap[index])<0)//And the value of the child is greater than the parent
        {
            //SWAP
            Sheep temp = heap[index/2];
            heap[index/2] = heap[index];
            heap[index] = temp;
            index = index/2;
        }
    }
    public Sheep peek()
    {
        if(heap == null)
            return null;
        return heap[0];
    }
    public Sheep removeSheep()
    {
        Sheep returnVal = peek();
         heap[0] = heap[size-1]; //index Out of bonunds error
         heap[size-1] = null;
         size--;
         climbDown();
        return returnVal;
    }
    public void climbDown()
    {
        int index = 0;
        while(index*2+1 < size)//While there is a left child
        {
            //Find smallest child
            int bigIndex = index*2+1;
            if(index*2+2 < size &&
                    heap[index*2+1].compareTo(heap[index*2+2])>0) //Right was bigger than left so change it
            {
                bigIndex = index*2+2;
            }
            if(heap[index].compareTo(heap[bigIndex])<0)//If current index is greater than smaller index
            {
                //SWAP
                Sheep temp = heap[index];
                heap[index] = heap[bigIndex];
                heap[bigIndex] = temp;
            }
            else
            {
                break;//We're done!
            }
            index = bigIndex;//Update the index to continue
        }
    }
    public void sheepRollCall()
    {
        for(Sheep thing : heap)
        {
            if(thing == null)
                break;
            System.out.println(thing.toString());
            System.out.println("");
        }
    }
    public static void sheepHeapSort(SheepHeapMain heap)
    {
        SheepHeapMain tempheap = heap;
        for(int i=size;i>0;i++)
        {
            System.out.println(tempheap.removeSheep()+" ");
            System.out.println();
        }
    }
}
//****************************************************************

public class SheepHeapTester {
    public static void main(String[] args) {
        final int heapSize = 15;
        SheepHeapMain heap = new SheepHeapMain(heapSize);
        heap.addSheep(new Sheep(55,"Jimmy"));
        heap.addSheep(new Sheep(43,"Ricky"));
        heap.addSheep(new Sheep(77,"Larry"));
        heap.addSheep(new Sheep(12,"Suzie Q"));
        heap.addSheep(new Sheep(91,"Curly"));
        heap.addSheep(new Sheep(85,"Bubba"));
        heap.addSheep(new Sheep(189,"MEGA SHEEP"));
        heap.addSheep(new Sheep(46,"Bo Peep"));
        heap.addSheep(new Sheep(27,"Queenie"));
        heap.addSheep(new Sheep(19,"Fluffy"));
        System.out.println("current thing is");
        heap.sheepRollCall();
        System.out.println();
        System.out.println("Sorted Sheepies :)");
        SheepHeapMain.sheepHeapSort(heap);
    }
}

您得到ArrayIndexOutOfBoundsException是因为您试图在heap数组中引用索引-1。

我添加了一行打印sizeheap.length:

public Sheep removeSheep()
    {
        System.out.println("removeSheep size: " + size + " array size: " + heap.length);
        Sheep returnVal = peek();
         heap[0] = heap[size-1]; //index Out of bonunds error
         heap[size-1] = null;
         size--;
         climbDown();
        return returnVal;
    }

这是输出:

Sorted Sheepies :)
removeSheep size: 10 array size: 15
Sheep [weight=189.0, name=MEGA SHEEP] 
removeSheep size: 9 array size: 15
Sheep [weight=77.0, name=Larry] 
removeSheep size: 8 array size: 15
Sheep [weight=27.0, name=Queenie] 
removeSheep size: 7 array size: 15
Sheep [weight=46.0, name=Bo Peep] 
removeSheep size: 6 array size: 15
Sheep [weight=19.0, name=Fluffy] 
removeSheep size: 5 array size: 15
Sheep [weight=55.0, name=Jimmy] 
removeSheep size: 4 array size: 15
Sheep [weight=43.0, name=Ricky] 
removeSheep size: 3 array size: 15
Sheep [weight=85.0, name=Bubba] 
removeSheep size: 2 array size: 15
Sheep [weight=91.0, name=Curly] 
removeSheep size: 1 array size: 15
Sheep [weight=12.0, name=Suzie Q] 
removeSheep size: 0 array size: 15
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at SheepHeapMain.removeSheep(SheepHeapMain.java:55)
    at SheepHeapMain.sheepHeapSort(SheepHeapMain.java:107)
    at SheepHeapTester.main(SheepHeapTester.java:24)

至于修复代码,这里有一个标准的堆排序算法,它使用最小堆按降序排序,您可以将其用作参考:

public class HeapSort {
  private static int getLeft(int index) {
      return index * 2 + 1;
  }
  private static int getRight(int index) {
      return index * 2 + 2;
  }
  private static void exchange (int[] arr, int first, int second) {
      int temp = arr[first];
      arr[first] = arr[second];
      arr[second] = temp;
  }
  private static void minHeapify (int[] arr, int size, int index) {
      int left = getLeft(index);
      int right = getRight(index);
      int minIndex = index;
      if (left < size && arr[left] < arr[minIndex]) 
        minIndex = left;
      if (right < size && arr[right] < arr[minIndex]) 
        minIndex = right;
      if (index != minIndex) {
          exchange(arr, index, minIndex);
          minHeapify (arr, size, minIndex);
      }
  }
  private static void buildMinHeap (int[] arr) {
      int size = arr.length;
      for (int i = ((size-1) / 2); i >= 0; i --) {
          // Do max-heapify on the i.
          minHeapify (arr, size, i);
      }
  }
  public static void heapSort(int[] arr) {
      int size = arr.length;
      buildMinHeap(arr);
      for (int i = size - 1; i >= 0; i--) {
          exchange (arr, 0, i);
          minHeapify (arr, i, 0);
          showArray(arr);
      }
  }
  public static void showArray (int[] arr) {
      int size = arr.length;
      for (int i = 0; i < size; i++)
          System.out.print(String.format("%-4d", arr[i]));
      System.out.println();
  }

  public static void main (String[] args) {
      int[] arr = {53, 42, 86, 11, 27, -5, 89, 0};
      heapSort(arr);
      showArray(arr);
  }
}

最新更新