手写 PriorityQueue的实现 java

本文主要是介绍手写 PriorityQueue的实现 java，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于一个堆结构来说，我们应用的很广。常见的就有我们学的八大排序之一的而堆排序。其实堆就是一个完全二叉树结构（逻辑结构），但我们真实实现的底层是基于数组。
首先，我们温故一下堆排序，然后通过这一理念对应想想PriorityQueue的一些方法于是我们就可以实现一些功能，这边我只实现一部分比较常用的功能。
先堆排序：
代码：

//用来交换数值
public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
//对于每次插入的数值确定具体在数结构中的位置
	public static void HeapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}
//这个则从上至下的遍历树结构看是否满足大分堆
	public static void HeapBy(int[] arr, int index, int heapsize) {
		int left = 2 * index + 1;
		while (left < heapsize) {
			// 左右孩子比较大小 并且左右孩子不能越界
			int larget = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
			larget = arr[larget] > arr[index] ? larget : index;
			if (larget == index)
				break;
			swap(arr, index, larget);
			index = larget;
			left = index * 2 + 1;
		}
	}
//抽取数据，然后进行再排序
	public static void HeapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			HeapInsert(arr, i);
		}
		int index = arr.length;
		swap(arr, 0, --index);
		while (index > 0) {
			HeapBy(arr, 0, index);
			swap(arr, 0, --index);
		}
	}

这样就是一个简单的大分堆排序。而接下来就是要实现PriorityQueue 部分功能。

//add添加数据其实还可以有其他限制，根据不同需求可以更改
public static void add(int []arr,int index) {
		int n=0;
		while(arr[n++]!=0) {
		}
		arr[n]=index;
		HeapSort(arr);
	}
//这里的find函数是对应PriorityQueue无法实现的改变堆结构的一个实现方法
//查找堆元素并删除。
	public static int[] find(int[] arr, int index) {
		int left = 0;
		int right = arr.length;

		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] > index) {
				right = mid;
			} else if (arr[mid] < index) {
				left = mid + 1;
			} else {
				arr[mid] = Integer.MIN_VALUE;
				break;
			}
		}
		int[] dp = new int[arr.length - 1];
		for (int i = 1; i < arr.length ; i++) {
			dp[i] = arr[i];
		}
		HeapSort(dp);
		return dp;
	}
//对应PriortyQueue的poll()
	public static int poll(int[] arr) {
		int n = arr[arr.length - 1];
		int[] dp = new int[arr.length - 1];
		for (int i = 0; i < arr.length - 1; i++) {
			dp[i] = arr[i];
		}
		arr = dp;
		return n;
	}
//返回最大值
	public static int Max(int[] arr) {
		return arr[arr.length - 1];
	}

这只是一种实现方式，效率以及空间上会有些许问题，有大佬有别的想法可以指点指点。

这篇关于手写 PriorityQueue的实现 java的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！