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

堆和优先队列

程序员文章站 2024-02-15 21:51:41
...

二叉堆
二叉堆是一颗完全二叉树,堆中的某个结点的值总是不大于父节点的值,通常这种堆称为最大堆(相应的可以定义最小堆)下层的某一元素不一定小于上层的某一元素,既然是完全二叉树,所以用数组定义该结构。
堆和优先队列

import java.util.Iterator;

import javax.print.attribute.standard.MediaSize.Other;

import com.oupeng.p1线性表.ArrayList;

public class MaxHeap<E extends Comparable<E>> implements Iterable<E> {
	private ArrayList<E> data;
	public MaxHeap() {
		data=new ArrayList<E>();
	}
	public void add(E e){
		data.addLast(e);
		siftUp(data.getSize()-1);
	}
	private void siftUp(int k) {
		while(k>0&&data.get(k).compareTo(data.get(parent(k)))>0){
			data.swap(k, parent(k));
			k=parent(k);
		}
	}
	public E findMax(){
		if(data.isEmpty()){
			throw new IllegalArgumentException("最大堆为空!");
		}
		return data.getFirst();
	}
	public E findMin(){
		if(data.isEmpty()){
			throw new IllegalArgumentException("最大堆为空!");
		}
		E min=data.get(0);
		for(int i=1;i<data.getSize();i++){
			if(data.get(i).compareTo(min)<0){
				min=data.get(i);
			}
		}
		return min;
	}
	public E extractMax(){
		E max=findMax();
		data.swap(0, data.getSize()-1);
		data.removeLast();
		siftDown(0);
		
		return max;
	}
	private void siftDown(int k) {
		while(leftChild(k)<data.getSize()){
			int j=leftChild(k);
			if(j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))>0){
				j=rightChild(k);
			}
			if(data.get(k).compareTo(data.get(j))<0){
				data.swap(k, j);
				k=j;
			}else{
				break;
			}
		}
	}
	public E repalce(E e){
		E res=findMax();
		data.set(0, e);
		siftDown(0);
		return res;
	}
	public int size(){
		return data.getSize();
	}
	public boolean isEmpty(){
		return data.isEmpty();
	}
	public void clear(){
		data.clear();
	}
	
	
	//toString equalse Iterator
	
	private int parent(int index){
		if(index==0){
			throw new IllegalArgumentException("没有父结点!");
		}
		return (index-1)/2;
	}
	private int leftChild(int index){
		return 2*index+1;
	}
	private int rightChild(int index){
		return 2*index+2;
	}
	@Override
	public Iterator<E> iterator() {
		return data.iterator();
	}
	@Override
	public boolean equals(Object obj) {
		if(obj==null){
			return false;
		}
		if(obj==this){
			return true;
		}
		if(obj instanceof MaxHeap){
			MaxHeap<E> otherHeap=(MaxHeap<E>) obj;
			return this.data.equals(otherHeap.data);
		}else{
			return false;
		}
	}
}