对于一个堆结构来说,我们应用的很广。常见的就有我们学的八大排序之一的而堆排序。其实堆就是一个完全二叉树结构(逻辑结构),但我们真实实现的底层是基于数组。
首先,我们温故一下堆排序,然后通过这一理念对应想想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]; }
这只是一种实现方式,效率以及空间上会有些许问题,有大佬有别的想法可以指点指点。