最小堆代码实现

package sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 最小堆排序
 * Created by liuwei on 16/3/7.
 */
public class MinHeap {

    private List<Integer> heap = null;

    public  MinHeap(){
        heap = new ArrayList<>();
    }

    public MinHeap(int[] nums){
        heap = new ArrayList<>(nums.length);
        for(int i=0; i<nums.length;i++){
            heap.add(nums[i]);
        }
        adjust();
    }

    public void addElement(int number){
        heap.add(number);
//        adjust();
        adjustFromDownToUp();
    }

    public int size(){
        return heap.size();
    }

    public boolean isEmpty(){
        for(Integer i : heap){
            return false;
        }
        return true;
    }

    public Integer getTop(){
        return isEmpty()? null:heap.get(0);
    }

    public Integer delTop(){
        if(isEmpty()) return null;
        int top = heap.remove(0);
        if(!isEmpty()){
            heap.add(0,heap.get(heap.size()-1));
            heap.remove(heap.size()-1);
//            adjust();
            adjustFromUpToDown();
        }
        return top;
    }

    private void swap(int i,int j){
        int tmp = heap.get(i);
        heap.set(i,heap.get(j));
        heap.set(j,tmp);
    }

    /**
     * 全局调整
     * */
    private void adjust(){
        if(size() <= 1) return;
        int i = size() - 1;
        int parent = 0;
        if(i % 2 == 1){
            parent = (i -1) / 2;
            if(heap.get(i) < heap.get(parent)){
                swap(i,parent);
            }
            i--;
        }
        while(i > 0){
            parent = (i - 1) / 2;
            int value = Math.min(heap.get(i-1),heap.get(i));
            if(value < heap.get(parent)){
                if(value == heap.get(i-1)){
                    swap(i-1,parent);
                }
                else{
                    swap(i,parent);
                }
            }
            i= i -2;
        }
    }

    //当删除一个元素的时候,是将最后一个元素,插入到之前第一个元素的位置,该元素后面是有序的,这时候自上向下调整
    private void adjustFromUpToDown(){
        if(size() < 2) return;
        int index = 0;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while(index < size() ){
            if(right < size()){
                int value = Math.min(heap.get(left),heap.get(right));
                if(value < heap.get(index)){
                    if(value == heap.get(left)){
                        swap(left,index);
                        index = left;
                    }
                    else{
                        swap(right,index);
                        index = right;
                    }
                    left = 2 * index + 1;
                    right = 2 * index + 2;
                }
                else{
                    return;
                }
            }
            else if(left < size()){
                if(heap.get(left) < heap.get(index)){
                    swap(left,index);
                }
                return;
            }
            else{
                return;
            }
        }
    }

    //当增加一个元素的时候,是插入到最后一个位置,这时候,前面是有序的,这时候自下而上的调整
    private void adjustFromDownToUp(){
        if(size() < 2) return;
        int index = heap.size() - 1;
        int parent = (index - 1) / 2;
        if(index % 2 == 1){
            if(heap.get(index) < heap.get(parent)){
                swap(index,parent);
                index = parent;
            }
            else{
                return;
            }
        }
        int left = 0, right = 0;
        while(index > 0){
            parent = (index - 1)/2;
            if(index % 2 == 1){
                left = index;
                right = index + 1;
            }
            else{
                left = index - 1;
                right = index;
            }
            int value = Math.min(heap.get(left),heap.get(right));
            if(value < heap.get(parent)){
                if(value == heap.get(left)){
                    swap(left,parent);
                }
                else{
                    swap(right,parent);
                }
                index = parent;
            }
            else{
                return;
            }
        }
    }


    public void show(){
        for(Integer i : heap){
            System.out.print(i+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] nums = {9,12,17,30,50,20,60,65,4};
        MinHeap heap = new MinHeap();
//        heap.show();
//        heap.addElement(49);
//        heap.show();
//        while(!heap.isEmpty()){
//            System.out.print(heap.delTop()+" ");
//        }
//        System.out.println();

        for(int i=0; i<nums.length;i++){
            heap.addElement(nums[i]);
//            heap.show();
        }

        while(!heap.isEmpty()){
            System.out.print(heap.delTop()+" ");
        }
        System.out.println();
    }
}