자 바 는 큰 무더기 와 작은 무 더 기 를 실현 한다

package jianzhiOffer;

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

/**
 *    
 * 
 * @author tao
 *
 */
public class MaxHeap> {
	private List mHeap; //          

	public MaxHeap() {

		this.mHeap = new ArrayList<>();
	}

	
	/**
	 *           (         )  ：       ， N            (2N+1)，       (2N+2)。
	 * 
	 * @param start
	 *            --           (               )
	 */
	protected void filterup(int start) {

		int c = start; //             
		int p = (c - 1) / 2; //            
		T tmp = mHeap.get(c); //        

		while (c > 0) {
			//                  
			int cmp = mHeap.get(p).compareTo(tmp);
			if (cmp >= 0) {
				//     
				break;
			} else {
				//         ，  
				mHeap.set(c, mHeap.get(p));
				c = p;
				p = (c - 1) / 2;
			}
		}
		//              
		mHeap.set(c, tmp);
	}

	
	/**
	 *           (                 )
	 *  ：       ， N            (2N+1)，       (2N+2)。
	 * 
	 * @param start
	 *            --           (   0，    1   )
	 * @param end
	 *            --     (               )
	 */
	protected void filterdown(int start, int end) {

		int c = start; //           
		int l = 2 * c + 1; //         
		T tmp = mHeap.get(c); //       (  )

		while (l <= end) {
			//              
			int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
			//    
			if (l < end && cmp < 0) {
				l++;
			}
			//               
			cmp = tmp.compareTo(mHeap.get(l));
			if (cmp >= 0) {
				//      ,   
				break;
			} else {
				//      ,  
				mHeap.set(c, mHeap.get(l));
				c = l; //          
				l = 2 * c + 1; //             
			}
		}
		mHeap.set(c, tmp);
	}

	
	/**
	 *           
	 * 
	 * @param data
	 */
	public void insert(T data) {

		int insertIndex = mHeap.size(); //        
		//            
		mHeap.add(data);
		//   filterup  ，     
		filterup(insertIndex);
	}

	
	/**
	 *        data  
	 * 
	 * @param data
	 * @return   -1    ,   0      
	 */
	public int remove(T data) {

		//     
		if (mHeap.isEmpty()) {
			return -1;
		}

		//   data       
		int index = mHeap.indexOf(data);
		if (index == -1) {
			return -1;
		}

		//        
		int size = mHeap.size();
		//    data  ，           ，    filterdown      
		mHeap.set(index, mHeap.get(size - 1)); //          
		mHeap.remove(size - 1); //         

		if (mHeap.size() > 1 && index < mHeap.size()) {
			//       
			filterdown(index, mHeap.size() - 1);
		}
		return 0;
	}
	
	
	@Override
	public String toString() {
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < mHeap.size(); i++) {
			sb.append(mHeap.get(i) + " ");
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		
		int a[] = {10, 40 ,30, 60, 90, 70, 20, 50 ,80};
		
		//   
		MaxHeap maxHeap = new MaxHeap<>();
		
		//    
		System.out.println("===       ：");
		for(int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
			maxHeap.insert(a[i]);
		}
		
		//      
		System.out.println("===       ：");
		System.out.println(maxHeap);
		
		//     85
		int data = 85;
		maxHeap.insert(data);
		System.out.println("===      " + data + "      ：");
		System.out.println(maxHeap);
		
		//    90
		data = 90;
		maxHeap.remove(data);
		System.out.println("===     " + data + "      ：");
		System.out.println(maxHeap);
		
	}
}