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