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

一种优先队列的实现(基于二叉堆)

程序员文章站 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

相关标签: 随笔 其他