Priority Queue with a find function - Fastest Implementation

user_481182 0
Viewed 10860

I am looking at implementing a priority queue with an added requirement, a find/search function which will tell whether an item is anywhere within the queue. So the functions will be: insert, del-min and find.

I am unsure whether I should use a Heap or a Self-balancing binary search tree. It appears PQs are usually implemented with a Heap, but I am wondering if there is any advantage in using a binary search tree since I also need that find function.

Furthermore, on average I'll be doing more inserts than deletes. I am also considering a d-ary heap. Basically, every second counts.

Thanks!

binary-tree priority-queue heap optimization types
7 Answers

Please, check this code. I coded this program and this is a priority queue with your needed functions.

1. Insert
2. Find
3. Delete
4. Show

You can try it. It's working perfectly. Here I added ascending order minimum number to maximum number.

I used the priority queue default function to do that with a switch case.

queue.push()
queue.pop()
queue.top()
queue.size()

C++ code:

#include<bits/stdc++.h>
#include <queue>
using namespace std;
void show_queue(
    priority_queue<int, vector<int>, greater<int> > data)
{
    priority_queue<int, vector<int>,greater<int> > myq = data;
    while (!myq.empty()) {
        cout << '\t' << myq.top();
        myq.pop();
    }
    cout << '\n';
}

int main()
{
    priority_queue<int, vector<int>,greater<int> > myp_queue;
    while(1)
    {

    int choice;
    cout<<"\nwhat do you want to do?"<<endl;
    cout<<"1. Insert \n2. Find \n3. Delete \n4. Show Queue \n\nchoice your option from above: ";
    cin>>choice;

    switch(choice)
        {
            case 1:
                int n;
                cout<<"Enter the value: " ;
                cin>>n;// Option 2 => Insert
                myp_queue.push(n);
                break;
            case 2:
                if(!myp_queue.empty()){
                    cout<<"\n"<<myp_queue.top()<<" is the minimum number"<<endl; // Find the minimum number.
                }else{
                    cout<<"\nEmpty Priority Queue"<<endl;
                }
                break;
            case 3:
                if(!myp_queue.empty()){
                    myp_queue.pop(); //Delete the minimum number from the queue
                    cout<<"\nSuccessfully Deleted"<<endl;
                }else{
                    cout<<"\nThere is no element to delete"<<endl;
                }
                break;
            case 4:
                if(!myp_queue.empty()){
                    show_queue(myp_queue); // Show full queue
                }else{
                    cout<<"\nEmpty Priority Queue"<<endl;
                }
                break;
            default:
                cout<<"\nYou are terminated!!! \nYou entered wrong input.\n"<<endl;
        }

    }
    return 0;
}
user_68484170
Related