﻿ 数据结构-堆实现优先队列(java)-C#教程_软件编程-脚本宝典

# 数据结构-堆实现优先队列(java)

## 数据结构-堆实现优先队列(java)

```//最大堆
import java.util.ArrayList;
public class Heap{
private ArrayList list=new ArrayList();//用数组实现堆

public Heap(){}
public Heap(E[] objects){
for(int i=0;i0){
int parentIndex=(currentIndex-1)/2;//找到该结点的父结点
if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){//与父节点比较
//如果当前结点的值大于父结点就交换位置
E temp=list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}
else
break;
currentIndex=parentIndex;
}
}

public E remove(){//删除并返回根结点,堆的特点是移除了根结点后还是堆
if(list.size()==0) return null;

E removeObject=list.get(0);
list.set(0, list.get(list.size()-1));//把最后一个结点放在根结点的位置
list.remove(list.size()-1);

int currentIndex=0;
while(currentIndex=list.size())break;
//比较左右孩子的值，使maxIndex指向值大的结点
int maxIndex=leftChildIndex;
if(rightChildIndexMyPriorityQueue.java  public class MyPriorityQueue {
private Heap heap=new Heap();//用堆实现优先队列
//入队列
public void enqueue(E e){
}
//出队列
public E dequeue(){
return heap.remove();//这移除出之后，堆会自己调整，还是一个新堆
}
public int getSize(){
return heap.getSize();
}

}

TestMyPriorityQueueMainClass.java

public class TestMyPriorityQueueMainClass {

public static void main(String[] args) {
// TODO Auto-generated method stub
Patient p1=new Patient("John",2);
Patient p2=new Patient("Tom",9);
Patient p3=new Patient("Jack",4);
Patient p4=new Patient("Michael",6);

MyPriorityQueue priorityQueue=new MyPriorityQueue<>();
priorityQueue.enqueue(p1);
priorityQueue.enqueue(p2);
priorityQueue.enqueue(p3);
priorityQueue.enqueue(p4);

while(priorityQueue.getSize()>0){
System.out.print(priorityQueue.dequeue()+"  ");
}
}
static class Patient implements Comparable{
private String name;
private int priority;
public Patient(String name,int priority){
this.name=name;
this.priority=priority;
}
public String toString(){
return name+"(priority:"+priority+")";
}
@Override
public int compareTo(Object oo) {//比较优先级
// TODO Auto-generated method stub
return this.priority-((Patient)oo).priority;
}

}
}

```
Tags：

﻿
<