Heap 堆

堆的Java实现：        

效果： 堆排序

83 83 83 77 75 74 73 72 62 55 53 44 39 34 34 33 31 30 28 24 23 22 22 19 19 18 11 6 2 2

 

import java.util.ArrayList;

/**
 * Data Structure -- Heap
 * @author Jason
 *
 */
public class Heap<T extends Comparable<T>> {

	// 堆是 完全二叉树，可以用数组存储
	ArrayList<T> items;
	
	public Heap(int cap)
	{	items = new ArrayList<T>(cap);	} 
	public Heap()
	{	items=new ArrayList<T>();		}
	
	// 添加，加到末尾，然后对末尾shift up
	public void add(T item)
	{
		items.add(item);
		shiftUp(items.size()-1);
	}
	// 删除堆顶，用末尾值替换 堆顶，然后对堆顶 shift down
	public T deleteMax()
	{
		if(items.isEmpty())	return null;
		T maxItem=items.get(0);
		T lastItem=items.remove(items.size()-1);
		if(items.size()!=0)
		{
			items.set(0, lastItem);
			shiftDown(0);
		}
		return maxItem;
	}
	
	// 如果父节点 小于 自己，上移
	void shiftUp(int index)
	{
		T me=items.get(index);
		int indexParent;
		while(index>0)
		{
			indexParent=(index-1)/2;
			if(me.compareTo(items.get(indexParent))>0)		// the son is larger than the father
			{
				items.set(index, items.get(indexParent));
				index=indexParent;
			}
			else break;
		}
		items.set(index, me);
	}
	// 如果 子节点中的较大值 大于 自己，交换下移
	void shiftDown(int index)
	{
		T me=items.get(index);
		int indexSon=index*2+1;	// left son right here
		while(indexSon<items.size())
		{
			// whether have right son, just get the largest son
			if(indexSon+1<items.size())
				indexSon= items.get(indexSon).compareTo(items.get(indexSon+1))>0? indexSon:(indexSon+1);
			
			if(me.compareTo(items.get(indexSon))<0)	// father is less than the son
			{
				items.set(index, items.get(indexSon));
				index=indexSon;
				indexSon=index*2+1;
			}
			else break;
		}
		items.set(index, me);
	}
	
	// 简单的添加，移出，相当于 堆排序
	public static void main(String[] args) {
		Heap<Integer> heap=new Heap<Integer>(100);   
        for(int i=0; i<30 ;i ++)   
        {   
            int temp=(int)(Math.random()*100);   
            heap.add(temp);   
        }   

        while(heap.items.size()!=0)
        {
        	System.out.print(heap.deleteMax()+" ");
        }
	}
}