Java 删除元素后最小堆减小数组大小
Java min heap decrease array size after removing element
我正在创建一个具有最小堆排序的优先级队列(我自己的数组形式),我正在执行一种方法,该方法删除优先级队列(我的数组)中的第一个元素,即根。然后,我再次调用我的数组上的 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?
我知道数组不能减少,但我看到它的所有实现都使用数组,所以必须有一些方法,比如创建一个新数组?
这是我的输出:
Before Heap Sort :
[1, 10, 16, 19, 3, 5]
After Heap Sort :
[1, 3, 5, 10, 16, 19]
After deleting :
Here there are duplicate 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
An array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. After creation, its length is fixed.
所以如果你想使用数组,你必须用你的新长度创建新数组。
并用旧数组的值填充新数组。 (请参阅第 link 中的 复制数组 部分)
解决方案是拥有一个 HeapSize int 值,每次删除元素时该值都会减少。下次在 for 循环中迭代数组时,我们不会超出堆大小。
我正在创建一个具有最小堆排序的优先级队列(我自己的数组形式),我正在执行一种方法,该方法删除优先级队列(我的数组)中的第一个元素,即根。然后,我再次调用我的数组上的 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?
我知道数组不能减少,但我看到它的所有实现都使用数组,所以必须有一些方法,比如创建一个新数组?
这是我的输出:
Before Heap Sort :
[1, 10, 16, 19, 3, 5]After Heap Sort :
[1, 3, 5, 10, 16, 19]After deleting :
Here there are duplicate 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
An array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. After creation, its length is fixed.
所以如果你想使用数组,你必须用你的新长度创建新数组。
并用旧数组的值填充新数组。 (请参阅第 link 中的 复制数组 部分)
解决方案是拥有一个 HeapSize int 值,每次删除元素时该值都会减少。下次在 for 循环中迭代数组时,我们不会超出堆大小。