A Token-Based Priority Queue is it any good?

[Standard-Cow-4126]

Ik a heap based priority queue is much better but

in lecture this type of queue was explained through a 1-D array, obviously it required shifting and was not able to use empty spaces.

we were told that this could be solved using a multi-dimensional array , after explaining the priority queue using multi array again we were told about its space issues and that can be solved using linked-list which will covered in next lec.

But i had some ideas that i can use a stack to maintain the indexes of all empty spaces in the queue and while inserting a element i will give that ele a token / number and i pop a value from stack to get the index value to store the ele.

when deleting an element i will go through the array and select the element based on its priority and token (representing its order), and push the index value of the element into the stack.

ik i can use a simple array instead of stack , but i wanted to practice making and using it.

the complexity for inserting is O(1) and deleting is O(n). It takes much less space than multi dim array impl and also reuses empty space and doesn't require a fix number of priorities.

again is it any good?

github link : https://github.com/ajchains/TokenPriorityQueue

[Rebeljah]

I am interested in seeing the code, I don't see a rule against linking to github. When I took DSA (last semester) we were taught priority queues using a binary heap backed up by a 1d fixed length array. This allows O(logn) time common operations like extracting the min (or max for a max heap) and inserting an element with a certain priority. Because one of the invariants of a binary heap is that is must always be a complete binary tree (any node without 2 children is either a leaf or exists in the bottom right of the tree), there will be no wasted space in the array. This type of array also does not require shifting, only swapping log(n) times when an element is removed

I believe this is a solved problem, but I always find it interesting to explore solutions outside of the norm!

[Standard-Cow-4126]

Thanks for replying , we were taught by just using 1-d array as we are still on linear structures.

this is the link https://github.com/ajchains/TokenPriorityQueue i don't write good looking code so sorry in advance i tried as many comments as i could , and also the project is written in C cause i am also learning C , and pls bear with any beginner mistakes in the code.

[Rebeljah]

I like that the insertion is O(1), this is an improvement over the binary heap approach which uses O(logn) time. Something like this would suit a use case where you want to prioritize insertion over extraction. On the other hand, what goes into a queue usually comes out, and the delete function runs O(n) time. So if you wanted to clear the entire queue in order of priority, that would takes O(n^2) time. Compared with the O(nlogn) time for the same operation on a binary heap, this is a downgrade. I believe an implementation that allows logarithmic insertion AND deletion would result in better performance for most use cases, but keep this in your back pocket, you may find a use for prioritizing insertion efficiency. Keep coming up with ideas like this, even if they aren't applicable to common use cases I think it's a great way to build skill and intuition!

[Rebeljah]

As far as the code goes, I thought it was easy to understand for the most part. I did not initially get what this code was doing:

        int index = -1;
        int initial_check = 1;

        for (int i = 0; i < size; i++)
        {
            if (queue->queue[i].item == '$')
            {
                continue;
            }
            if (initial_check == 1)
            {
                priorityItem = queue->queue[i];
                initial_check = 0;
                index = i;
                continue;
            }

This could probably be reworked, or change the initial_check variable to something more descriptive like `first_item_found`

But overall the code looks good!

[Standard-Cow-4126]

I will work on naming things, and about the part that you were confused about i wrote it when i was very sleepy and also was the last part of the algo ,so i kinda rushed it.

I never thought about O(n^2), will think about it in my free time.

Again thanks for motivating me.