データ構造--ヒープ

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

/**
 * 
 *     :       
 * 
 * @version 2.0.0
 * @author zhiminchen
 */
public class MinHeap> {

    //       E  
    private E[] data;
    //               
    private int size;

    public MinHeap(int capacity) {
        data = (E[]) new Comparable[capacity];
        size = 0;
    }

    public MinHeap() {
        this(16);
    }

    /**
     *     array  ，   
     * 
     * @param array
     */
    public MinHeap(E[] array) {
        data = (E[]) new Comparable[array.length];
        //  array     data   
        for (int i = 0; i < data.length; i++) {
            data[i] = array[i];
        }
        size = array.length;
        //          siftDown  ，            
        for (int i = parent(array.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 
     *     :         
     * 
     * @return boolean
     * @version 2.0.0
     * @author zhiminchen
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 
     *     :         
     * 
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    public int size() {
        return size;
    }

    /**
     * 
     *     :   index     
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int parent(int index) {
        if (index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    /**
     * 
     *     :   index      
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int left(int index) {
        return 2 * index + 1;
    }

    /**
     * 
     *     :   index       
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int right(int index) {
        return 2 * index + 2;
    }

    /**
     * 
     *     :        element
     * 
     * @param element void
     * @version 2.0.0
     * @author zhiminchen
     */
    public void add(E element) {
        if (size >= data.length) {
            resize(data.length * 2);
        }

        data[size] = element;

        siftUp(size);
        size++;
    }

    /**
     * 
     *     :        ,   
     * 
     * @return E
     * @version 2.0.0
     * @author zhiminchen
     */
    public E remove() {
        if (size <= 0) {
            return null;
        }
        E ret = data[0];
        //                 
        data[0] = data[size - 1];
        data[size - 1] = null;
        //  size    
        size--;
        //             ，        
        siftDown(0);
        return ret;
    }

    /**
     * 
     *     :          
     * 
     * @return E
     * @version 2.0.0
     * @author zhiminchen
     */
    public E findMin() {
        if (size == 0)
            throw new IllegalArgumentException("Can not findMin when heap is empty.");
        return data[0];
    }

    /**
     * 
     *     :  index         ，       
     * 
     * @param index void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void siftDown(int index) {
        int left = left(index);
        //        left>=size              
        if (left >= size) {
            return;
        }
        //   index          
        E min = data[left];
        //   index                 ， index              
        if (left + 1 < size && min.compareTo(data[left + 1]) > 0) {
            min = data[left + 1];
            left = left + 1;
        }
        //  index                ，     ，    
        if (data[index].compareTo(min) > 0) {
            swap(index, left);
            siftDown(left);
        }
    }

    /**
     * 
     *     :  index        ，        
     * 
     * @param size2 void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void siftUp(int index) {
        //        
        if (index <= 0) {
            return;
        }
        // index        ，      
        if (data[index].compareTo(data[parent(index)]) < 0) {
            swap(index, parent(index));
            //     ，    
            siftUp(parent(index));
        }
    }

    /**
     * 
     *     :      a, b   
     * 
     * @param a
     * @param b void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void swap(int a,
                      int b) {
        E temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }

    /**
     * 
     *     :       
     * 
     * @param capacity void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void resize(int capacity) {
        E[] temp = (E[]) new Object[capacity];
        for (int i = 0; i < data.length; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("heap size : %d capacity : %d ", size, data.length));
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        Random random = new Random();
        int n = 100;
        Integer array[] = new Integer[n];
        for (int i = 0; i < 100; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }

        MinHeap heap = new MinHeap(array);

        System.out.println(heap);

        List list = new ArrayList();
        while (!heap.isEmpty()) {
            list.add(heap.remove());
        }

        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) > list.get(i)) {
                throw new RuntimeException();
            }
        }

    }
}