java - 删除元素后Java最小堆减小数组大小
问题描述
我正在创建一个具有最小堆排序的优先级队列(我自己的数组形式),其中我正在实现一个方法,该方法删除作为根的优先级队列(我的数组)中的第一个元素。然后我再次在我的数组上调用该heapifyNumbers()
方法以再次对最小堆中的数组进行排序。问题只是我不能从数组中减少,所以最后两个元素将是重复的。
这是我正在创建的删除方法
public void deleteMinimum(int[] array){
array[0] = array[array.length - 1];
heapSort(array);
//here I want to decrease array size by 1 after heap sorting the array
}
这里我只是将第一个索引替换为最后一个索引,然后再次调用heapifyNumbers()
我的数组上的方法对数组进行排序。如何将数组大小减少 1?我知道数组不能减少,但我看到所有使用数组的实现,所以必须有某种方法,比如创建一个新数组?
这是我的输出:
堆排序之前:
[1, 10, 16, 19, 3, 5]堆排序后:
[1, 3, 5, 10, 16, 19]删除后:
这里有重复的 19
[3、5、10、16、19、19]
我已经这样做了,arr = Arrays.copyOf(array, array.length -1);
但我不知道它是否仍然保持 Log N 时间复杂度
如果您有兴趣,这是我的完整代码:
import java.util.*;
public class ObligatoriskOpgave2 {
int[] arr={1,10,16,19,3,5};
public static void buildheap(int []arr) {
/*
* As last non leaf node will be at (arr.length-1)/2
* so we will start from this location for heapifying the elements
* */
for(int i=(arr.length-1)/2; i>=0; i--){
heapifyNumbers(arr,i,arr.length-1);
}
}
public static void heapifyNumbers(int[] arr, int i, int size) {
int left = 2*i+1;
int right = 2*i+2;
int max;
if(left <= size && arr[left] > arr[i]){
max=left;
} else {
max=i;
}
if(right <= size && arr[right] > arr[max]) {
max=right;
}
// If max is not current node, swapCurrentNodeWithMaximumOfChildren it with max of left and right child
if(max!=i) {
swapCurrentNodeWithMaximumOfChildren(arr,i, max);
heapifyNumbers(arr, max,size);
}
}
public static void swapCurrentNodeWithMaximumOfChildren(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static int[] heapSort(int[] arr) {
buildheap(arr);
int sizeOfHeap=arr.length-1;
for(int i=sizeOfHeap; i>0; i--) {
swapCurrentNodeWithMaximumOfChildren(arr,0, i);
sizeOfHeap=sizeOfHeap-1;
heapifyNumbers(arr, 0,sizeOfHeap);
}
return arr;
}
public void deleteMinimum(int[] array){
array[0] = array[array.length - 1];
heapSort(array);
}
public static void main(String[] args) {
ObligatoriskOpgave2 o = new ObligatoriskOpgave2();
System.out.println("Before Heap Sort : ");
System.out.println(Arrays.toString(o.arr));
o.arr=heapSort(o.arr);
System.out.println("=====================");
System.out.println("After Heap Sort : ");
System.out.println(Arrays.toString(o.arr));
o.deleteMinimum(o.arr);
System.out.println(Arrays.toString(o.arr));
}
}
解决方案
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
数组是一个容器对象,它包含固定数量的单一类型的值。数组的长度是在创建数组时确定的。创建后,它的长度是固定的。
所以如果你想使用数组,你必须用你的新长度创建新数组。
并用旧数组的值填充新数组。(请参阅第一个链接中的复制数组部分)
推荐阅读
- react-native-android - 在 android 中构建 react 本机应用程序时出现错误
- c# - 我们如何在一个项目中添加实体框架并在另一个项目中将其用作服务?
- npm - 在 NPM 脚本中找不到模块自动前缀
- java - 如何在android中共享图像和文本
- android - 在 3.0.2 版本中找不到 ToothPickRule 类
- javascript - 如何允许在多项选择中选择多个文件?
- google-cloud-platform - 使用 Logback 的控制台 JSON Appender 记录到 Stackdriver
- sql - 这里的语法不正确?
- javascript - MapBox 无法处理大量数据 | Javascript
- node.js - 在 Mongoose 中使用初始不存在的字段