2

Здравствуйте. Не могу понять принцип вставки в приоритетную очередь, а конкретно сдвига вверх. К примеру я имею массив состоящий из 6 элементов.

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

И хочу внести в него элемент 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++;
    }
} 

Я прохожу по массиву, до тех пор пока значение item не превысит j-е значение. Т.е при j = 2, queArray[j] будет равен 15. Далее нужно сдвинуть элементы вверх. За это по идее должна отвечать эта часть:

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

Но ведь таким образом, я не увеличиваю размер массива и не двигаю его, я просто присваиваю queArray[j+1] значению queArray[j], 20 = 15 и таким образом просто убираю значение 20 из массива и заменяю его на 15. Где я неправ?

3
  • сдвиг начинается с предпоследнего элемента и затрет последний, да
    – etki
    13 дек 2016 в 19:24
  • Почему с предпоследнего, если сдвинуть нужно после 15, т.е. после j = 2;? И разве можно в очереди, просто затирать элемент, вместо сдвига. Это пример из алгоритмов и структур данных Лафора. Мб там код неверный, вы не могли бы проверить? 13 дек 2016 в 19:42
  • потому что цикл начинается с nItems - 1 и идет вниз
    – etki
    13 дек 2016 в 19:43

2 ответа 2

3

У вас обычный массив. При инициализации ему присваивается фиксированная длина в 6 элементов. Добавить элементы в массив не получится. Можно только менять уже имеющиеся.

Для того, чтобы добавлять/менять/удалять нужно использовать не обычный массив а ArrayList.

Так вы сможете просто добавить элемент в ArrayList и сортировать с помощью компаратора

2

Так к слову, у Вас идет обычная инициализация массива(фиксированный размер) и это никак не очередь. Для более детального изучения проблемы почитайте про такие коллекции, реализующие интерфейс Queue.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.