Efficient priority queue

Details Efficient priority queue Efficient priority queue

1998-07-15

1999-12-14

Sheikh, Ayaz R.

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus access regulation

710100, 710111, 707100, 707103, 709213, G06F 1318

Patent

active

060031018

ABSTRACT:
A priority queue structure and algorithm for managing the structure which in most cases performs in constant time. In other words, most of the time the inventive algorithm performs its work in an amount of time that is independent on the number of priority classes or elements that exist in the queue. The queue itself consists of a linked list of elements ordered into subqueues corresponding to priority classes, with higher priority subqueues appearing earlier in the queue. An array of priority pointers contains an entry for each subqueue that points to the last element of each subqueue. Elements are removed for processing from the top of the queue. Removal takes constant time. Items are inserted into an appropriate subqueue by linking it at the end of its respective subqueue. The only case that requires a variable amount of time depending on the length of the queue and the number of priority classes occurs when an item is added to an empty subqueue which is of lower priority than the element at the top of the queue. All subsequent additions to that subqueue consume constant time until the subqueue becomes empty once again. A feature of the invention prevents the possibility of perpetually locking out lower priority items in the queue by promoting the priority of a preempted item residing directly below a newly inserted item on the queue.

REFERENCES:
patent: 4320455 (1982-03-01), Woods et al.
patent: 5521916 (1996-05-01), Choudhury et al.
patent: 5752028 (1998-05-01), Ellacott
patent: 5870396 (1999-02-01), Abu-Amara et al.
patent: 5903776 (1999-05-01), Larson

Affiliated with

Also associated with

Rating

Efficient priority queue does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient priority queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient priority queue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-874170