questions Inserting in heapsort

问题:

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

       }
   }

As I understand, I Insert the element at last. Then compare it with its parent. If parent is greater than this latest insertion, return the element. Else swap parent and this 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);
      }  
   }   
}

Thank you everybody, now i can make a children and parent node, but How can add insert method ? I think about while or if statement. But cannot fingure out...

回答1:

Think about what a heap is ... a COMPLETE tree.

                           0
                        1     2
                      3   4  

So the children of index 0 are index 1 and 2, the children of index 1 are 3 and 4, the children of index 2 are 5 and 6. See a pattern?

EDIT: also you should use generics for a heap, that is the reason why you are supposed to use an ArrayList in java and not a standard array. A generic heap will allow an argument to be past to determine the type so the structure is more flexible.

回答2:

In a 0-based binary heap, given a node at index i:

• The left child is at index (i * 2) + 1
• The right child is at index (i * 2) + 2
• The parent is at index (i - 1)/2

To insert, you add the item as the last item in the array, and then you move it up the heap, continually comparing with the parent. Like this:

public void insert(Student elt)
{
    students.add(elt);
    int i = students.size()-1;
    while (i > 0)
    {
        int p = parent(i);
        if (students[i] >= students[p])
        {
            // item is not smaller than parent, so we're done
            break;
        }
        // swap child and parent items
        swap(p, i);

        // and then move up one level
        i = p;
    }
}