java 堆排序

package wangChaoPA实习工作练习.com.进阶篇.排序;
import java.util.ArrayList;

/**
*
* <p>
* 描述该类情况 {@link 代表跟谁有关系}
* </p>
*
* @author 王超
* @since 1.0
* @date 2017年5月10日下午5:44:42
* @see 新建|修改|放弃
* @see wangChaoPA实习工作练习.com.进阶篇.排序.Heap
*/

public class Heap<E extends Comparable>
{
   private ArrayList<E> list = new ArrayList<E>();// 使用ArrayList实现堆排序

   public Heap()
   {
   }

   public Heap(E[] objects)
   {
       for (int i = 0; i < objects.length; i++)
       {
           add(objects[i]);
       }
   }

   // 添加
   public void add(E newObject)
   {
       // 添加到list
       this.list.add(newObject);
       // 获取到添加到list中newObject的索引值
       int currentIndex = this.list.size() - 1;
       while (currentIndex > 0)
       {
           // 获取到父节点的索引
           int parentIndex = (currentIndex) / 2;
           // 如果新增元素的值大于父节点的值则进行swap
           if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0)
           {
               E temp = this.list.get(currentIndex);
               this.list.set(currentIndex, this.list.get(parentIndex));
               this.list.set(parentIndex, temp);
           }
           else
           {
               break;
           }
           currentIndex = parentIndex;
       }
   }

   // 堆的大小
   public int getSize()
   {
       return this.list.size();
   }

   // 删除
   public E remove()
   {
       if (this.list.size() == 0)
       {
           return null;
       }
       // 首元素即最大的元素
       E removeObject = this.list.get(0);
       // 把最后的一个元素置于第一个
       this.list.set(0, this.list.get(this.list.size() - 1));
       // 删除最后一个元素
       this.list.remove(this.list.size() - 1);
       int currentIndex = 0;
       while (currentIndex < this.list.size())
       {
           // 获取到新首元素的子节点索引
           int leftChildIndex = currentIndex * 2 + 1;
           int rightChildIndex = currentIndex * 2 + 2;
           if (leftChildIndex >= this.list.size())
           {
               break;
           }
           // 获取子节点中大的索引值
           int maxIndex = leftChildIndex;
           if (rightChildIndex < this.list.size())
           {
               if (this.list.get(maxIndex)
                       .compareTo(this.list.get(rightChildIndex)) < 0)
               {
                   maxIndex = rightChildIndex;
               }
           }
           // 比较父节点与子节点并交换
           if (this.list.get(currentIndex)
                   .compareTo(this.list.get(maxIndex)) < 0)
           {
               E temp = this.list.get(maxIndex);
               this.list.set(maxIndex, this.list.get(currentIndex));
               this.list.set(currentIndex, temp);
               currentIndex = maxIndex;
           }
           else
           {
               break;
           }
       }
       return removeObject;
   }
}

//测试类
package wangChaoPA实习工作练习.com.进阶篇.排序;
public class HeapSort
{
   public static <E extends Comparable> void heapSort(E[] list)
   {
       Heap<E> heap = new Heap<E>();
       for (int i = 0; i < list.length; i++)
       {
           heap.add(list[i]);
       }
       for (int i = list.length - 1; i >= 0; i--)
       {
           list[i] = heap.remove();
       }
   }

   public static void main(String[] args)
   {
       Integer[] list =
       { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
       heapSort(list);
       for (Integer temp : list)
       {
           System.out.print(temp + " ");
       }
   }
}