Hello. I can not understand the principle of insertion into the priority queue, and specifically the shift up. For example, I have an array consisting of 6 elements.

int[] j = {5, 10, 15, 20, 25, 30};

And I want to add item = 16;

 public void insert(long item) // Вставка элемента { int j; if(nItems==0) // Если очередь пуста, queArray[nItems++] = item; // вставляем в ячейку 0 else // Если очередь содержит элементы { for(j=nItems-1; j>=0; j--) // Перебор в обратном направлении { if( item > queArray[j] ) // Если новый элемент больше, queArray[j+1] = queArray[j]; // сдвинуть вверх else // Если меньше, break; // сдвиг прекращается } queArray[j+1] = item; // Вставка элемента nItems++; } }

I go through the array until the item value exceeds the jth value. Ie when j = 2, queArray[j] will be equal to 15. Next, you need to move the elements up. For this, in theory, this part should be responsible:

 queArray[j+1] = queArray[j];

But in this way, I do not increase the size of the array and do not move it, I simply assign queArray[j+1] to queArray[j] , 20 = 15 and thus simply remove the value 20 from the array and replace it with 15. Where I wrong?

  • the shift begins with the penultimate element and overwrites the last one, yes - etki
  • Why from the penultimate, if you need to move after 15, i.e. after j = 2; ? And is it possible in the queue, just rub the element, instead of a shift. This is an example of the algorithms and data structures of Lafor. MB code is wrong there, could you check? - Kojer Defor
  • because the cycle starts with nItems - 1 and goes down - etki

2 answers 2

You have a regular array. When initialized, it is assigned a fixed length of 6 elements. Add items to the array will not work. You can only change existing ones.

In order to add / change / delete you need to use not a regular array but ArrayList .

So you can simply add an element to an ArrayList and sort it using a comparator

    So by the way, you have the usual array initialization (fixed size) and this is not a queue. For a more detailed study of the problem, read about such collections that implement the Queue interface.