[If this fits more to stackoverflow then transfer it there please.]
Hi, I’m trying to implement a priority queue in C.
The easiest way I found to do it is with a circular array (rather than using a linked list).
I have an array of fixed size, the index for the first element in the queue and the index for the next free place in the queue.
But I’m struggling with dequing the maximum value…
I know how to get the maximum value, but not how to move next and first so that the queue stays contiguous in the array (the only way I know of it working).
How should I do this? Or do you have a suggestion for a better implementation?
Thanks
0
The problem with using an array (circular or not) as underlying data structure for a priority queue is that you must always copy elements around to create a hole where a new element should be inserted or to fill the hole created by removing an element.
In a very naive implementation, using your circular array, you could use the following scheme:
- When adding an element, always add it at the position indicated by
nextand incrementnext. - When removing an element, copy the element indicated by
firstto the position just vacated and incrementfirst.
This scheme is easy to implement, but has the large drawback that you must loop over the entire (used portion of the) array to find the element with the highest priority.
For learning exercises, that is not a big deal, but you definitely want to avoid that in production code.
In production code, it is better to use a data structure that is continuously kept ordered on the priority of the items, so that the item with the highest priority is always at the front. This can be done with arrays (preferably regular, non-circular arrays) or linked lists. Linked lists may have a performance advantage because it is easier to add elements to the middle and to remove the first element without having to touch a bunch of other elements.
2
As a simple fix you can swap the max element with first and then pop as normal.
However I suggest using a max-heap structure. This has the advantage of having only O(log n) time complexity for push and pop and can fit in your fixed size array.
Popping a value involves putting the last element in the head and shifting it down. Pushing a value involves pushing to the end and shifting it up (or recursively shifting the direct parent down until it is in place).
2
Don’t use a circular array at all. It’s way simpler and more efficient to just use a regular array where you fill gaps by swapping with the backmost value of the array, and only manipulate the end index when you add or remove elements.
As said by others, a binary heap is the standard way to implement a priority queue, and you will benefit from this same overwrite-to-remove strategy when implementing a binary heap.
push (int i) {
// Make sure it's not full first!
array[end_index++] = i;
}
int pop () {
// Make sure it's not empty first!
// Set max_index to index the maximum value
int result = array[max_index];
array[max_index] = array[--end_index];
}