JAVA实现堆+堆排序【数据结构·堆排序】

JAVA实现堆+堆排序【数据结构·堆排序】

堆是一种完全二叉树，往往用数组存储而不像其他二叉树用二叉链表存储.
下面是实现Heap类的代码

public class Heap > {
    private java.util.ArrayList list = new java.util.ArrayList<>();

    public Heap(){

    }

    public Heap(E[] objects){
        for(int i=0;i 0){
            int parentIndex = (currentIndex-1)/2;
            if(list.get(currentIndex).compareTo(
                    list.get(parentIndex) ) > 0){
                E temp = list.get(currentIndex);
                list.set(currentIndex,list.get(parentIndex));
                list.set(parentIndex,temp);
            } else {
                break;
            }
            currentIndex = parentIndex;
        }
    }

    public E remove(){
        if(list.size() == 0)
            return null;
        E removerObject = list.get(0);
        list.set(0,list.get(list.size()-1));
        list.remove(list.size()-1);

        int currentIndex = 0;
        while(currentIndex < list.size()){
            int leftChildIndex = 2*currentIndex+1;
            int rightChileIndex = 2*currentIndex+2;

            if(leftChildIndex >= list.size())
                break;
            int maxIndex = leftChildIndex;
            if(rightChileIndex < list.size()){
                if(list.get(maxIndex).compareTo(
                        list.get(rightChileIndex))<0){
                    maxIndex = rightChileIndex;
                }
            }

            if(list.get(currentIndex).compareTo(
                    list.get(maxIndex)) < 0){
                E temp = list.get(maxIndex);
                list.set(maxIndex,list.get(currentIndex));
                list.set(currentIndex,temp);
                currentIndex = maxIndex;
            } else {
                break;
            }
        }
        return removerObject;
    }

    public int getSize(){
        return list.size();
    }

}

下面是堆对数组排序的堆排序代码

public class HeapSort {
    public static > void heapSort(E[] list){
        Heap heap = new Heap<>();

        for(int i=0;i=0;i--){
            list[i] = heap.remove();
        }
    }

    //测试方法
    public static void main(String[] args) {
        Integer[] list = {-44,-5,-3,3,3,1,-4,0,1,2,4,5,53};
        heapSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i]+" ");
        }
    }
}

测试通过