JavaHeapSort

java建堆和堆排序

public class HeapTest {

    public static void main(String[] args) {
        int[] data = {15, 13, 1, 5, 20, 12, 8, 9, 11};
        create(data);
//        heapSort(data);
//        insert(data);
        delete(data);
        for(Integer i : data){
            System.out.println(i);
        }
    }

    public static void create(int[] data){
        int size = data.length;
        int pos = (size - 2) / 2;
        while(pos >= 0){
            //建立小顶堆
            shiftDownMin(data,pos,size-1);
            pos--;
        }
    }

    /**
     * 建完堆后再排序
     * @param data
     */
    public static void heapSort(int[] data){
        for(int i = data.length - 1; i >= 0; i--){
            int temp = data[i];
            data[i] = data[0];
            data[0] = temp;
            shiftDownMin(data,0,i-1);
        }
    }

    /**
     * 建完堆后删除，删除只能删除堆顶节点
     */
    public static void delete(int[] data){
        data[0] = data[data.length - 1];
        shiftDownMin(data,0,data.length-2);
    }

    /**
     * 建完堆后再插入
     * @param data
     */
    public static void insert(int[] data){
        data[data.length-1] = 0;
        shiftUp(data,data.length-1);
    }

    public static void shiftUp(int[] data, int start){
        int i = start;
        int temp = data[i];
        int j = (start - 1) / 2;
        while(i > 0){
            if(data[j] <= temp){
                break;
            }
            data[i] = data[j];
            i = j;
            j = (i - 1) / 2;
        }
        data[i] = temp;
    }


    /**
     * 建立小顶堆
     * @param data
     * @param pos
     * @param size
     */
    public static void shiftDownMin(int[] data, int pos, int size){
        int i = pos;
        int temp = data[i];
        int j = pos * 2 + 1;
        while(j <= size){
            if(j < size && data[j] > data[j+1]){
                j++;
            }
            if(temp < data[j]){
                break;
            }
            data[i] = data[j];
            i = j;
            j = i * 2 + 1;
        }
        data[i] = temp;
    }

}