Я создаю приоритетную очередь (свою собственную в виде массива) с минимальной сортировкой кучи, где я реализую метод, который удаляет первый элемент в приоритетной очереди (мой массив), который является корневым. Затем я снова вызываю метод 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));
}
}