Java 学习+面试指南:https://javaxiaobear.cn
1、API设计
类名 | MaxPriorityQueue |
构造方法 | MaxPriorityQueue(int capacity):创建容量为capacity的MaxPriorityQueue对象 |
成员方法 | private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素 private void each(int i,int j):交换堆中i索引和j索引处的值 public T delMax():删除队列中最大的元素,并返回这个最大元素 public void insert(T t):往队列中插入一个元素 private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置 private void sink(int k):使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置 public int size():获取队列中元素的个数 public boolean isEmpty():判断队列是否为空 |
成员变量 | private T items:用来存储元素的数组 private int N:记录堆中元素的个数 |
2、代码实现
public class MaxPriorityQueue<T extends Comparable<T>> {
private T[] items;
private int size;
public MaxPriorityQueue(int capacity){
items = (T[]) new Comparable[capacity + 1];
size = 0;
}
/**
* 判断堆中索引i处的元素是否小于索引j处的元素
* @param i
* @param j
* @return true
*/
private boolean less(int i,int j){
return items[i].compareTo(items[j]) < 0;
}
/**
* 交换堆中i索引和j索引处的值
* @param i
* @param j
*/
private void each(int i,int j){
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
/**
* 删除队列中最大的元素,并返回这个最大元素
* @return
*/
public T delMax(){
T max = items[1];
each(1,size);
items[size] = null;
size--;
sink(1);
return max;
}
/**
* 往队列中插入一个元素
* @param t
*/
public void insert(T t){
items[++size] = t;
swim(size);
}
/**
* 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
* @param k
*/
private void swim(int k){
while (1 < k){
//比较k是否小于k/2,如果小于则交换元素
if(less(k/2,k)){
each(k/2,k);
}
k = k/2;
}
}
/**
* 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
* @param k
*/
private void sink(int k){
while (2 * k <= size){
int max = 2 * k;
//如果存在右子结点
if(2 * k + 1 <= size){
if(less(2*k,2*k+1)){
max = 2 * k + 1;
}
}
//比较当前结点和子结点中的较大者,如果当前结点不小,则结束循环
if(!less(k,max)){
break;
}
each(k,max);
k = max;
}
}
/**
* 获取队列中元素的个数
* @return
*/
public int size(){
return size;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
}
- 测试类
public class MaxPriorityQueueTest {
public static void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F", "G"};
MaxPriorityQueue<String> queue = new MaxPriorityQueue(10);
for (String s : arr) {
queue.insert(s);
}
System.out.println(queue.size());
String max;
while (!queue.isEmpty()){
max = queue.delMax();
System.out.print(max+ " ");
}
}
}
输出结果
7
G F E D C B A
标签:优先,Java,索引,队列,items,元素,private,int,public From: https://blog.51cto.com/xiaobear/11899808