一种优先队列的实现(基于二叉堆)
程序员文章站
2022-07-10 18:58:49
package com.example;import java.util.Comparator;import java.util.Objects;public class H20200724 {public static void main(String[] args) throws Exception {H20200724 parentClass = new H20200724();Utils utils = parentClass.new Util...
package com.example;
import java.util.Comparator;
import java.util.Objects;
public class H20200724 {
public static void main(String[] args) throws Exception {
H20200724 parentClass = new H20200724();
Utils<Integer> utils = parentClass.new Utils<Integer>();
/**
* 数据源准备
*/
System.out.println("数据源:");
Integer[] ready2Work = new Integer[21];
for (int i = 0, len = ready2Work.length; i < len; i++) {
ready2Work[i] = (int) (Math.random() * 20);
}
System.out.println("[" + utils.toString("],[", ready2Work, 0, ready2Work.length) + "]");
/**
* 二叉堆运作
*/
int M = 5;
System.out.println("二叉堆运作结果:(选择最大的" + M + "个)");
Heap<Integer> heap = parentClass.new Heap<Integer>(M);
heap.storeData(ready2Work);
heap.work();
System.out.println(heap.toString());
/**
* 检验二叉堆运作情况
*/
System.out.println("参考组:");
QSort3Way<Integer> qSort = parentClass.new QSort3Way<Integer>();
qSort.storeData(ready2Work);
qSort.work();
System.out.println(qSort.toString());
}
/**
* 优先队列接口
*
* @author H20200724
*
* @param <K>
*/
public interface PQueue<K extends Comparable<K>> {
public K deleteHeadElement();
public void insertElement(K e) throws Exception;
}
/**
* 二叉堆
*
* @author H20200724
*
* @param <K>
*/
public class Heap<K extends Comparable<K>> extends WorkFlow<K> implements PQueue<K> {
private int N = 0;
private int size = 0;
public static final int DEFAULT_SIZE = 10 + 1;
public Heap(int size, Comparator<K> c) {
this(size);
initializeComparator(c);
}
public Heap(int size) {
if (size >= 1) {
this.size = size + 1;
} else {
this.size = DEFAULT_SIZE;
}
}
public Heap(Comparator<K> c) {
this();
initializeComparator(c);
}
public Heap() {
this.size = DEFAULT_SIZE;
}
@SuppressWarnings("unchecked")
private void swim(int k) {
while (k > 1 && (this.isUserCustomComparator ? less((K) this.elements[k / 2], (K) this.elements[k], this.c)
: less((K) this.elements[k / 2], (K) this.elements[k]))) {
swap(this.elements, k / 2, k);
k = k / 2;
}
}
@SuppressWarnings("unchecked")
private void sink(int k) {
while (2 * k <= this.N) {
int j = 2 * k;
if (j < this.N
&& (this.isUserCustomComparator ? less((K) this.elements[j], (K) this.elements[j + 1], this.c)
: less((K) this.elements[j], (K) this.elements[j + 1])))
j++;
if (!(this.isUserCustomComparator ? less((K) this.elements[k], (K) this.elements[j], this.c)
: less((K) this.elements[k], (K) this.elements[j])))
break;
swap(this.elements, k, j);
k = j;
}
}
@SuppressWarnings("unchecked")
@Override
public K deleteHeadElement() {
K headElement = (K) this.elements[1];
swap(this.elements, 1, this.N--);
sink(1);
return headElement;
}
@Override
public void insertElement(K e) throws Exception {
this.elements[++this.N] = e;
swim(this.N);
}
@Override
public String toString() {
try {
return "[" + toString("],[", this.elements, 1, this.N + 1) + "]";
} catch (Exception e) {
e.printStackTrace();
}
return "";
}
@SuppressWarnings("unchecked")
@Override
public void work() throws Exception {
initializeElements();
int len = this.elements.length;
if (this.storeDatas != null && this.storeDatas.length > 0) {
for (int i = 0, storeLen = this.storeDatas.length; i < storeLen; i++) {
System.out.print("【" + this.toString() + " <- " + this.storeDatas[i].toString());
if (this.N == len - 1) {
K h = deleteHeadElement();
System.out.print("; -> " + h.toString());
}
insertElement((K) this.storeDatas[i]);
System.out.println("】 ====> " + this.toString());
}
}
}
@Override
public void initializeElements() {
this.elements = new Object[this.size];
}
}
/**
* 排序接口
*
* @author H20200724
*
*/
public interface Sort {
public void sort(int leftBorder, int rightBorder);
}
/**
* 一种采用[小于,等于,大于]基准元素,切割区域分成这三个区域的快速排序
*
* @author H20200724
*
* @param <K>
*/
public class QSort3Way<K extends Comparable<K>> extends WorkFlow<K> implements Sort {
public QSort3Way(Comparator<K> c) {
Objects.requireNonNull(c);
initializeComparator(c);
}
public QSort3Way() {
}
@Override
public void sort(int leftBorder, int rightBorder) {
if (leftBorder >= rightBorder)
return;
int[] benchmark = partition(leftBorder, rightBorder);
sort(leftBorder, benchmark[0] - 1);
sort(benchmark[1] + 1, rightBorder);
}
@SuppressWarnings("unchecked")
public int[] partition(int leftBorder, int rightBorder) {
K benckmark = (K) this.elements[leftBorder];
int i = leftBorder;
int m = i + 1;
int j = rightBorder;
while (m <= j) {
int r = this.isUserCustomComparator ? this.c.compare(benckmark, (K) this.elements[m])
: benckmark.compareTo((K) this.elements[m]);
if (r == 0)
m++;
else if (r > 0)
swap(this.elements, i++, m++);
else
swap(this.elements, j--, m);
}
return new int[] { i, j };
}
@Override
public void work() throws Exception {
initializeElements();
sort(0, this.elements.length - 1);
}
@Override
public void initializeElements() {
Objects.requireNonNull(this.storeDatas);
this.elements = new Object[this.storeDatas.length];
System.arraycopy(this.storeDatas, 0, this.elements, 0, this.storeDatas.length);
}
@Override
public String toString() {
try {
return "[" + toString("],[", this.elements, 0, this.elements.length) + "]";
} catch (Exception e) {
e.printStackTrace();
}
return "";
}
}
/**
* 工具类
*
* @author H20200724
*
* @param <T>
*/
public class Utils<T extends Comparable<T>> {
public void swap(Object[] arr, int a, int b) {
if (arr == null || arr.length < 0 || a < 0 || b < 0 || a >= arr.length || b >= arr.length)
return;
Object t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public String toString(CharSequence de, Object[] arr, int begin, int len) throws Exception {
Objects.requireNonNull(de);
Objects.requireNonNull(arr);
if (len > arr.length) {
throw new Exception("数组越界");
}
if (begin < 0) {
throw new Exception("开始遍历的指针异常");
}
StringBuilder sb = new StringBuilder();
for (int i = begin; i < len; i++) {
if (i != begin) {
sb.append(de).append(arr[i].toString());
} else {
sb.append(arr[i].toString());
}
}
return sb.toString();
}
@SuppressWarnings("unchecked")
public boolean less(Comparable<T> a, Comparable<T> b) {
Objects.requireNonNull(a);
Objects.requireNonNull(b);
return a.compareTo((T) b) <= 0;
}
@SuppressWarnings("unchecked")
public boolean less(Comparable<T> a, Comparable<T> b, Comparator<T> c) {
Objects.requireNonNull(a);
Objects.requireNonNull(b);
return c.compare((T) a, (T) b) <= 0;
}
}
/**
* 算法工作流接口
*
* @author H20200724
*
* @param <K>
*/
public abstract class WorkFlow<K extends Comparable<K>> extends Utils<K> {
protected Object[] elements;
protected Object[] storeDatas;
protected boolean isUserCustomComparator = false;
protected Comparator<K> c;
@SuppressWarnings("unchecked")
public void storeData(K... datas) {
Objects.requireNonNull(datas);
this.storeDatas = new Object[datas.length];
for (int i = 0, len = datas.length; i < len; i++) {
this.storeDatas[i] = datas[i];
}
}
public void initializeComparator(Comparator<K> c) {
this.c = c;
this.isUserCustomComparator = true;
}
public abstract void work() throws Exception;
public abstract void initializeElements();
}
}
本文地址:https://blog.csdn.net/luhuidong1/article/details/107572207
上一篇: jdbc简单的操作流程(四)删除
下一篇: Android基础知识—数据持久化