优先队列数据结构 [英] priority queue data structure

问题描述

假设我有一个优先级队列，按照递增的顺序删除元素，并且存储在这个队列中的元素是元素 1，1，3，0，1 。增加的顺序是 0 然后 1 然后 3 ，但有三个元素 1 s。

当我调用删除它将首先删除 0 ，但是如果我再次调用删除，那么它将同时删除所有三个 1 ，或者我需要调用删除三次单独删除所有 1 元素。

在这样的优先级队列中调用删除是否删除相同最小值的所有元素，或每次调用只删除一个元素？

解决方案

通常，在优先级队列中，删除操作会删除包含最大值的单个记录。所以在你的情况下，这将是第二个选择。删除的顺序不能保证。任何具有最大值的键将被删除。此外，未排序的数组是实现优先级队列的不良数据结构。您通常会使用堆数据结构来获取O（log（n））的插入和删除保证。

Suppose that I have a priority queue which removes elements in increasing order, and stored in this queue are the elements 1, 1, 3, 0, 1. The increasing order is 0 then 1 then 3, but there are three element 1s.

When I call remove it will first remove the 0, but if I call remove again will it remove all three 1s at the same time, or will I need to call remove three separate times to remove all of the 1 elements.

Does a call to remove on such a priority queue remove all elements of the same minimum value or will only one element be removed with each call?

解决方案

In a priority queue usually the remove operation removes a single record containing the maximum value. So in your case it would be the second option. The order of removal is not guaranteed. Any key with the "maximum" value would be removed. Also, unsorted array is a bad data structure of implement a priority queue. You would typically use a heap data structure to get O(log(n)) guarantees on insertion and removal.

这篇关于优先队列数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！