Очевидно, что любой стек умеет часть того, что требуется. Причём большую часть, чем priority queue. Тем не менее, стек не годится.
Кроме того, подразумеваемым обычно свойством priority queue является частичное НЕсохранение порядка, в то время как нам нужно держать порядок точно.
Короче говоря, страшно далеки они от того, что надо. Впрочем, решение с амортизированным O(1) я, как уже говорил, придумал, а ниже привели решение с настоящим O(1). И ни то, ни другое не имеет отношения к priority queue.
no subject
Date: 2014-03-25 06:04 pm (UTC)Кроме того, подразумеваемым обычно свойством priority queue является частичное НЕсохранение порядка, в то время как нам нужно держать порядок точно.
Короче говоря, страшно далеки они от того, что надо. Впрочем, решение с амортизированным O(1) я, как уже говорил, придумал, а ниже привели решение с настоящим O(1). И ни то, ни другое не имеет отношения к priority queue.
> array-backed binary heap?
Она, родимая.