ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
27
Рис. 5. Операция вставки в IgushArray
Для удаления одного элемента из позиции
k
в IgushArray необхо-
димо:
1)
получить доступ к удаляемому элементу
,
,
i j
E
сложность
О
(1);
2)
удалить элемент в очереди
i
D
в позиции
j
,
сложность
( )
D
O S
;
3) «
сдвинуть» элементы в этой и следующих очередях вверх, для
чего требуется:
3.1)
вынуть элемент с начала следующей очереди
1
i
D
+
,
слож-
ность
О
(1);
3.2)
вставить в конец текущей очереди
i
D
,
сложность
О
(1).
Каждый сдвиг имеет сложность
О
(1).
Необходимо «сдвинуть»
вверх порядка
V
S
элементов, тогда сложность всего «сдвига» состав-
ляет
( )
( )
2 1
V
V
S O O S
=
.
Примечание
.
Операция может потребовать удаление последней очереди
(
в случае, если последняя очередь до операции имеет один элемент, после
операции — пустая).
Псевдокод операции удаления:
//
доступ к позиции
/
_
i
k deq size
= ⎢
⎥
⎣
⎦
[ ]
i
D V i
=
1 2
...
...
...
...
...
...
...
K
O(1)
O(1)
O(1)
O(S
D
)
...
...
...
...
...