一种优先队列的实现（基于二叉堆）

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