heap.java~2~

冒泡排序、折中排序

package hi_lo;
/*
    *This class implements the heapsort algorithm.
    *This class can sort only integers.
*/




public class Heap {

  /**
   * IMplements the heap
   */
  private int[] heap;

  /**
   * Stores the sorted list
   */

  private int[] sortedList;

  //method here


  public void setData(int[] data)
  {
    heap = new int[data.length];
    sortedList = new int[data.length];

    for(int i = 0; i < data.length; i++)
    {
      heap[i] = data[i];
    }
  }

  public int[] sort()
  {
    construct();   //perform the constructions phase

    extract();    //perform the extraction phase

    return sortedList;
  }

  private void construct()
  {
    int current, maxChildIndex;
    boolean done;

    for(int i = (heap.length - 2)/2; i >= 0; i--)
    {

      current = i;
      done = false;

      while(!done)
      {
        //perform one rebuild step with the node at index i


        if(2 * current + 1 > heap.length - 1)
        {
          //current node has no children, so stop
          done = true;
        }
        else
        {
          //current node has at least one child,get the index of larger child

          maxChildIndex =  maxChild(current, heap.length - 1);

          if(heap[current] < heap[maxChildIndex])
          {
            //a child is larger,so swap and continue
            swap(current, maxChildIndex);
            current = maxChildIndex;
          }
          else
          {
            //the value relationshiop constraint is statisfied,so stop
            done = true;
          }
        }
      }
    }
    testPrint(heap.length);   //temp
  }


  private void extract()
  {
    int current, maxChildIndex;
    boolean done;

    for(int size = heap.length - 1; size >= 0; size--)
    {
      //remove the root node data
      sortedList[size] = heap[0];

      //move the last node to the root
      heap[0] = heap[size];

      //rebuild the heap with one less element
      current = 0;
      done = false;

      while(!done)
      {
        if( 2 * current + 1 > size)
        {
          //current node has no children, so stop
          done = true;
        }
        else
        {
          //current node has at least one child,
          //get the index of larger child
          maxChildIndex = maxChild(current,size);

          if(heap[current] < heap[maxChildIndex])
          {
            //a child is larger, so swap and contine
            swap(current,maxChildIndex);
            current = maxChildIndex;
          }
          else
          {
            //value relationshiop constraint is staisfied, so stop
            done = true;
          }
        }
      }
      testPrint(size);   //temp
    }
  }

  private int maxChild(int location,int end)
  {
    //precondition: node at location has at least one chile

    int result,leftChildIndex,rightChildIndex;

    rightChildIndex = 2 * location + 2;
    leftChildIndex =  2 * location + 1;

    if(rightChildIndex <= end &&
       heap[leftChildIndex] < heap[rightChildIndex])
    {
      result = rightChildIndex;
    }
    else
    {
      result = leftChildIndex;
    }

    return result;
  }

  private void swap(int loc1,int loc2)
  {
    int temp;

    temp = heap[loc1];
    heap[loc1] = heap[loc2];
    heap[loc2] = temp;
  }

  private void testPrint(int limit)
  {
    for(int i = 0; i < limit; i++)
    {
      System.out.print(" " + heap[i]);
    }

    System.out.println();
  }

}