欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Heap 堆

程序员文章站 2022-04-08 13:52:43
...

堆的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()+" ");
        }
	}
}

 

相关标签: UP