堆和优先队列
程序员文章站
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;
}
}
}
上一篇: swagger2(接口文档)