java - 问题插入heapsort

Question

import java.util.ArrayList;
import java.util.Collection;

public class MaxHeap
{
   private ArrayList<Student> students;

   public MaxHeap(int capacity)
   {
      students = new ArrayList<Student>(capacity);
   }

   public MaxHeap(Collection<Student> collection)
   {
      students = new ArrayList<Student>(collection);
      for(int i = size()/2; i >= 0; i--)
      {
         maxHeapify(i);
      }
   }

   public Student getMax()
   {
      if(size() < 1)
      {
         throw new IndexOutOfBoundsException("No maximum value:  the heap is empty.");
      }
      return students.get(0);
   }

   public Student extractMax()
   {
      Student value = getMax();
      students.set(0,students.get(size()-1));
      students.remove(size()-1);
      maxHeapify(0);
      return value;
   }


   public void insert(Student elt)
   {

       private int lastOne;

       if (lastOne ==  students.length)
           throw new heapException("heap is full");
       else {
           // I'm stuck here

       }
   }

据我了解，我最后插入了元素。然后将它与它的 parent 进行比较。如果 parent 大于此最新插入，则返回该元素。否则交换 parent 和这个 child

    private int parent(int index)
   {
      return (index - 1)/2;
   }

   private int left(int index)
   {
      return 2 * index + 1;
   }

   private int right(int index)
   {
      return 2 * index + 2;
   }

   private int size()
   {
      return students.size();
   }

   private void swap(int from, int to)
   {
      Student val = students.get(from);
      students.set(from,  students.get(to));
      students.set(to,  val);
   }

   private void maxHeapify(int index)
   {
      int left = left(index);
      int right = right(index);
      int largest = index;
      if (left <  size() && students.get(left).compareTo(students.get(largest)) > 0)
      {
         largest = left;
      }
      if (right <  size() && students.get(right).compareTo(students.get(largest)) > 0)
      {
         largest = right;
      }
      if (largest != index)
      {
         swap(index, largest);
         maxHeapify(largest);
      }  
   }   
}

谢谢大家，现在我可以制作子节点和父节点了，但是如何添加插入方法呢？我考虑 while 或 if 语句。但是想不通...

Answer 1

想想堆是什么……一棵完整的树。

                           0
                        1     2
                      3   4  

所以索引 0 的 child 是索引 1 和 2，索引 1 的 child 是 3 和 4，索引 2 的 child 是 5 和 6。看到一个模式了吗？

编辑:您还应该对堆使用泛型，这就是为什么您应该在 java 中使用 ArrayList 而不是标准数组的原因。通用堆允许通过参数来确定类型，因此结构更加灵活。