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

java数组实现优先队列

程序员文章站 2022-06-06 23:45:09
...

定义:结点大于两个子结点的二叉树
使用堆来实现优先队列
从1开始存储
有子结点的2倍为父结点
如 a[1] 的子结点为 a[2],a[3],
a[2]的子结点为a[4],a[5]
队列的入队可以看成叶子结点的上浮
队列的出队可以看成跟结点的下沉

上浮算法

public void swim(int k) {
		while(k > 1&& a[k/2]<a[k]) {
			int n = a[k/2];
			a[k/2] = a[k];
			a[k] = n;
			k=k/2;
		}	
	}

下沉算法

public void sink(int k) {
		while(2*k<=N) 
		{
			int j = k*2;
			if(j<N&&a[j]<a[j+1]) j++;
			if(a[k]>a[j]) break;
			int n = a[j];
			a[j] = a[k];
			a[k] = n;
			k = j;
		}
	}

if(j<N&&a[j]<a[j+1]) j++; 如果j=N,则无需判断a[j]<a[j+1],防止索引超出范围,此时j为最后的叶子结点

完整代码

package Mr_math;

import java.util.Random;

public class Tqueue {
	private int []a;
	private int N = 0;
	public Tqueue(int size) {
		a = new int[size+1];
		for(int i = size;i>0;i--) {
			a[i] = 0;
		}
	}
	public boolean empty() {
		return N>=1;
	}
	public int size() {
		return N;
	}
	public void swim(int k) {
		while(k > 1&& a[k/2]<a[k]) {
			int n = a[k/2];
			a[k/2] = a[k];
			a[k] = n;
			k=k/2;
		}	
	}
	public void sink(int k) {
		while(2*k<=N)
		{
			int j = k*2;
			if(j<N&&a[j]<a[j+1]) j++;
			if(a[k]>a[j]) break;
			int n = a[j];
			a[j] = a[k];
			a[k] = n;
			k = j;
		}
	}
	public void insert(int v) {
		a[++N] = v;
		swim(N);
		System.out.println();
		for(int i=N;i>=1;i--) {
			System.out.print("   "+a[i]);
		}
	}
	public int del() {
		int max = a[1];
		int n = a[N];
		a[N] = a[1];
		a[1] = n;
		a[N--] = 0;
		sink(1);
		return max;
	}
	public static void main(String[] args) {
		int N=10;
		Tqueue  q = new Tqueue(N);
		Random out = new Random();
		for (int i = 0; i < N; i++) {
			System.out.println();
			int a = out.nextInt(1000);
			System.out.println();
			System.out.print("  插入:  "+a);
			System.out.println();
			q.insert(a);
		}
		System.out.println();
		for(int i=q.size();i>1;i--) {
		System.out.println("弹出:"+q.del());
		}
	}
	
	
	
	
	
	
	
	
}

输出结果:
java数组实现优先队列
java数组实现优先队列