MaxHeap && PriorityQueue

/**
 * class MaxHeap
 * @author Administrator
 *
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    
    /**
     * constructor
     * @param capacity
     */
    public MaxHeap(int capacity) {
        data = new Array<>(capacity);       
    }
    
    public MaxHeap() {
        data = new Array<>();
    }
    
    /**
     * method-->isEmpty
     * @return
     */
    public boolean isEmpty() {
        return data.getSize() == 0;
    }
    
    /**
     * method-->getSize
     * @return
     */
    public int getSize() {
        return data.getSize();
    }
    
    /**
     * method-->get the parent index of target
     * @param index
     * @return
     */
    public int parent(int index) {
        return (index-1)/2;
    }
    
    /**
     * method-->get the left child index of target
     * @param index
     * @return
     */
    public int leftChild(int index) {
        return 2*index+1;
    }
    
    /**
     * method-->get the right child index of target
     * @param index
     * @return
     */
    public int rightChild(int index) {
        return 2*index+2;
    }
    
    /**
     * method-->add a new element into the heap
     * add the element into the tail of heap,then execute siftUp
     * @param e
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize()-1);
    }
    
    private void siftUp(int k) {
        if (k < 0 || k> data.getSize()-1) {
            throw new IllegalArgumentException("Illegal index");
        }
        while(k>0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
            /**
             * swap index is an array-level operation
             * we can encapsulate this operation in the Array class
             */
            data.swap(k, parent(k));
            /**
             * vital detail !!!!
             * update the k for the next iteration
             */
            k = parent(k);
        }       
    }
    /**
     * method --> get maximum element
     * @return
     */
    public E findMax() {
        return data.get(0);
    }   
    
    /**
     * method --> extract the maximum from the heap
     * @return
     */
    public E extractMax() {
        // swap the location of the maximum and minimum
        data.swap(0, data.getSize()-1);
        // remove the last elements,the operation is removing the prior maximum
        data.removeLast();
        // sink the prior minimum element
        siftDown(0);
        return findMax();
    }
    
    private void siftDown(int k) {
        if (k<0 || k>data.getSize()-1) {
            throw new IllegalArgumentException("Illegal index");
        }
        
        // until the index of left child of target > size
        while(leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j+1<data.getSize() && data.get(j+1).compareTo(data.get(j))>0) {
                data.swap(k, j+1);
                k = j+1;
            }
            
            if (data.get(k).compareTo(data.get(j))>=0) {
                break;
            }       
            data.swap(k, j);
            k = j;
        }                       
    }
}       


**基于最大堆可以实现优先队列**:



/**
 * 
 * @author Administrator
 *
 * @param <E>
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
    private MaxHeap<E> heap;
    
    public PriorityQueue() {
        heap = new MaxHeap<>();
    }
    
    @Override
    public int getSize() {
        return heap.getSize();
    }
    
    @Override
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    @Override
    public E getFront() {
        return heap.findMax();
    }
    
    @Override
    public E dequeue() {
        return heap.extractMax();
    }
    
    @Override
    public void enqueue(E e) {
        heap.add(e);
    }
    
}