current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite

[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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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 next and increment next.
  • When removing an element, copy the element indicated by first to the position just vacated and increment first.

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.

share|improve this answer
    
Thanks, but I think I'll stick with the array because I only have a maximum of 256 elements. One question though, "When removing an element, copy the element indicated by first to the position just vacated and increment first.", can you elaborate on what you mean by that? –  shoham Jul 11 at 10:54
    
@shoham: In pseudocode: i = find_highest_prio_element(); temp = element[i]; element[i] = element[first]; first++; return temp;. –  Bart van Ingen Schenau Jul 11 at 11:19
up vote 4 down vote

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).

share|improve this answer
    
I'm not really good at this big O notation, but as far as I see it, I have O(1) for enqueuing and O(n) for dequeuing, considering I do 256 enqueuing and 256 dequeuing, which is better? –  shoham Jul 11 at 10:44
    
honestly for small N implementation details trump the big O, only way to know is to profile –  ratchet freak Jul 11 at 10:45
up vote 0 down vote

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];
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.