0

I have priority_queue. My function delete not very rational in terms of memory consumption and time. I've seen similar themes, but they did not help me.

How to remove element not at top from priority_queue?

STL Priority Queue - deleting an item

How i can delete elements on log( n ).

My function:

1

void deleteFromTimeQueue(const K& key)
            {
                std::priority_queue<Record<K>, std::vector<Record<K>>, Comparator<K>> tmpTimeQueue_;

                while (timeQueue_.size() > 0)
                {
                    Record<K> it = timeQueue_.top();

                    if (it.getKey() == key)
                    {
                        timeQueue_.pop();
                        break;
                    }
                    tmpTimeQueue_.push(it);
                    timeQueue_.pop();
                }

                while (tmpTimeQueue_.size() > 0)
                {
                    Record<K> it = tmpTimeQueue_.top();
                    timeQueue_.push(it);
                    tmpTimeQueue_.pop();
                }
            }

How i can delete elements whitout tmpTimeQueue_?

2

void deleteFromTimeQueue(const K& key)
        {
            std::priority_queue<Record<K>, std::vector<Record<K>>, Comparator<K>> tmpTimeQueue_;

            while (timeQueue_.size() > 0)
            {
                Record<K> it = timeQueue_.top();

                if (it.getKey() == key)
                {
                    timeQueue_.pop();
                    continue;
                }
                tmpTimeQueue_.push(it);
                timeQueue_.pop();
            }
            timeQueue_.swap(tmpTimeQueue_);
        }

What number better 1 or 2?

Community
  • 1
  • 1
Tipok
  • 675
  • 8
  • 26

1 Answers1

1

Maybe implementing Priority-queue using LINK-LIST can be a good ideal. By that, you can search for the element and delete it as normal link list. Hope this can be helpful for you.

shylonezeng
  • 26
  • 4
  • Unfortunately this also means you have O(n) complexity for every insert as well. It may be an option for the OP if the list is small enough, but as a general solution, heaps are considerably more efficient for what priority queues are *supposed* to be used for: insertions and *front*-removals. I'd rather introduce an O(NlogN) for exception cases if it meant my mainline kept O(logN). – WhozCraig Jan 13 '15 at 09:52