CN100511152C - Method for managing priority queue - Google Patents

Abstract

The invention discloses a management method of priority queues. An index table including insertion positions of different priority queue units is configured for each priority queue, and all insertion positions in the index table are initialized to empty addresses, and new queue units are inserted into the When arriving at the priority queue, the method also includes: step A, determining the insertion position of the new queue unit according to the priority of the new queue unit and the insertion position information in the index table, and inserting the new queue unit according to the determined insertion position Insert into the priority queue; step B, refresh the insertion position in the index table. Adopting the technical solution provided by the present invention, when inserting the queue unit into the queue, only need to search in the index table with the priority of the queue unit to be inserted as the index number to determine the insertion position, instead of starting from one end of the queue , compare each queue unit to determine the insertion position, thereby improving the processing speed when inserting queue units, and making it easier to manage the priority queue.

Description

A Management Method of Priority Queue

technical field

The invention relates to computer application technology, in particular to a management method of a priority queue.

Background technique

In message processing that supports priority, the messages waiting to be processed by the processing module are arranged in the order of priority, not in the order of request processing. That is to say, even if a message with a higher priority is requested to be processed later than a message with a lower priority, it should be processed before a message with a lower priority.

Priority queues enable priority-aware message processing. Each queue unit of the priority queue encapsulates a message with priority, and the priority of the queue unit is the priority of the message. In the priority queue, the queue units are arranged from the head of the queue to the tail of the queue in order of priority from low to high, that is, the queue unit at the head of the queue has the lowest priority, and the queue unit at the end of the queue has the highest priority. Queue units with the same priority are arranged in sequence according to the time when they are inserted into the queue. The queue units that are inserted into the queue first are arranged near the end of the queue, and the queue units that are inserted into the queue later are arranged near the head of the queue. The processing module processes the messages encapsulated by each queue unit one by one from the end of the queue, and deletes the processed queue units from the priority queue.

In the prior art, if there is a queue unit to be inserted into the priority queue, it is necessary to compare the priority of each queue unit with the priority of the current queue unit to be inserted one by one from the queue head or queue tail, to determine where to insert. Taking the comparison from the head of the queue as an example, if the comparison finds that the priority of the previous queue unit is lower than that of the current queue unit to be inserted, and the priority of the latter queue unit is not lower than that of the current queue unit to be inserted priority, the current queue unit to be inserted should be inserted between the previous queue unit and the next queue unit.

In practical applications, there are many queue units in the priority queue. In the prior art, every time a queue unit is inserted into a priority queue, it needs to be compared one by one from one end of the queue. Usually, a large number of comparison operations are required to determine the insertion position. In the worst case, the entire queue needs to be traversed to determine the insertion position. position before the insert operation itself. In this way, the average time required to determine the insertion position is far greater than the time required for the insertion operation itself, thus causing a waste of processing power, that is, a large amount of processing power is used for comparison when determining the insertion position, thereby reducing Ability to handle other tasks.

Contents of the invention

In view of this, the main purpose of the present invention is to provide a management method for priority queues, so as to improve the processing speed of priority queues.

In order to achieve the above object, the present invention provides a management method of priority queues, configuring index tables including insertion positions of different priority queue units for each priority queue, and initializing the index tables to be empty addresses for all elements, When inserting a new queue unit into the priority queue, the method also includes:

Step A, according to the priority of the new queue unit and the insertion position information in the index table, determine the insertion position of the new queue unit, and insert the new queue unit into the priority queue according to the determined insertion position;

Step B, refresh the insertion position in the index table.

Wherein, the refresh insertion position described in step B includes:

Step B1, judge whether the priority of the new queue unit is the highest priority, if so, end the current refresh process, otherwise execute step B2;

Step B2, taking the priority of the new queue unit plus 1 as the current index number;

Step B3, read the insertion position corresponding to the current index number in the index table, and judge whether the read insertion position needs to be modified, if it needs to be modified, execute step B4, otherwise end the current refresh process;

Step B4, modify the insertion position corresponding to the current index number to the address of the new queue unit, and judge whether the current index number is equal to the highest priority, if so, end the current refresh process, otherwise execute step B5;

In step B5, add 1 to the current index number as a new current index number, and return to step B3.

Wherein, the insertion position of the new queue unit determined according to the priority of the new queue unit and the index table in step A is:

The priority of the new queue unit is used as the index number, and the insertion position corresponding to the index number in the index table is used as the storage address of the queue unit before the new queue unit when the new queue unit is inserted into the priority queue.

Wherein, the judgment in step B3 whether it is necessary to modify the read insertion position is:

Judging whether the insertion position corresponding to the current index is equal to any one of the empty address or the insertion address of the new queue unit, if it is, it is considered that the read insertion position needs to be modified, otherwise it is considered that the read insertion position does not need to be modified. insert position.

Wherein, the method further includes:

Step C, delete the queue unit at the end of the queue from the priority queue, and refresh the insertion position of the index table.

Wherein, the step C includes:

Step C1, judge whether the insertion position corresponding to the highest priority as the index number in the index table is an empty address, if yes, execute step C6, otherwise delete the queue unit at the end of the queue from the priority queue, and execute step C2 ;

Step C2, using the priority of the queue unit deleted in step C1 plus 1 as the current index number;

Step C3, assign the value of the forward pointer data item in the queue unit deleted in step C1 to the insertion position corresponding to the current index number in the index table, and then judge whether the value of the current index number is equal to the highest priority, and if so, execute the step C5, otherwise execute step C4;

Step C4, add 1 to the value of the current index number as the new current index number, return to step C3;

Step C5, delete the queue unit at the end of the queue from the priority queue, and end this processing flow;

In step C6, it is determined that the priority queue is an empty queue, and no queue unit can be deleted therefrom.

Wherein, the queue unit positioned at the tail of the queue is deleted from the priority queue as:

The value of the forward pointer data field of the deleted queue unit is given to the queue tail pointer data field in the queue description corresponding to the priority queue; the value of the forward pointer data field of the deleted queue unit is the address, and will be stored in The next item pointer data field of the queue unit at the address is changed to a null address.

By adopting the technical scheme provided by the present invention, an index table is configured for each priority queue, and when the queue unit is inserted into the queue, it is only necessary to search the index table with the priority of the queue unit to be inserted as the index number. The insertion position can be determined instead of starting from one end of the queue and comparing each queue unit to determine the insertion position, thereby improving the processing speed when inserting a queue unit and making it easier to manage the priority queue.

Description of drawings

Fig. 1 is the schematic diagram of the priority queue provided by the present invention;

Fig. 2 is the flow chart when inserting queue unit in the management method of priority queue provided by the present invention;

Fig. 3 is the schematic diagram of the priority queue provided by the present invention after being inserted into the queue unit;

Fig. 4 is a flow chart of deleting a queue unit in the priority queue management method provided by the present invention.

Detailed ways

The core idea of the present invention is to configure an index table for each priority queue, and when inserting a queue unit into the priority queue, determine the insertion position information according to the insertion position information recorded in the index table corresponding to the priority of the queue unit one by one. position, and the index table is dynamically refreshed when queue units are inserted into and deleted from the priority queue.

In order to make the purpose, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

In the present invention, each priority queue is composed of several queue units and a queue description.

Each queue unit corresponds to a message, and the message pointer data item in the queue unit is equal to the storage address of the corresponding message; the priority data item of the queue unit is equal to the priority of the corresponding message; the forward pointer data item of the queue unit is equal to the priority queue The storage address of the next queue unit closer to the queue head than itself, the forward pointer of the queue unit at the queue head is an empty address; the backward pointer data item of the queue unit is equal to the queue unit closer to the queue end than itself in the priority queue The storage address of the next queue unit, the back pointer of the queue unit at the end of the queue is a null address. In the present invention, the next queue unit that is closer to the head of the queue relative to a certain queue unit is called a forward queue unit, and the next queue unit that is closer to the end of the queue relative to a certain queue unit is called a backward queue unit . An empty address can be regarded as a special queue unit, that is, a queue unit with an empty address does not have any data items, and can be used as a forward queue unit or as a backward queue unit.

The queue description has three data items: queue head pointer, queue tail pointer and index table. Wherein the queue head pointer data item is equal to the storage address of the queue unit located at the head of the queue; the queue tail pointer data item is equal to the storage address of the queue unit located at the queue tail; the index table stores a new queue unit with a certain priority in the priority queue insertion position.

The index number in the index table corresponds to the priority that the priority queue can handle. For example, when the priority queue can handle 20 priorities, the index number in the index table is 1 to 20; the data type of the index table element is pointer type. When building a new priority queue, initialize all elements of the index table to empty addresses.

The value of each element in the index table indicates that the new queue unit whose message priority data item is equal to the index number of the element, when inserted into the priority queue, should be inserted after the queue unit whose address is the value of the element. If the value of an element is a null pointer, it means that the new queue unit whose message priority data item is equal to the index number of this element should be inserted at the head of the queue when it is inserted into the priority queue.

Please refer to FIG. 1 , which is a schematic diagram of a priority queue provided by the present invention.

For the priority queue shown in Figure 1, suppose the number of priorities that the priority queue can handle is 5, and the address of queue unit 1 is 1000, the address of queue unit 2 is 1008, and the address of queue unit 3 is 1006 . The corresponding index table is shown in Table 1. That is to say, for a queue unit with a priority of 1, when inserted into the priority queue, it should be inserted at the head of the queue; for a queue unit with a priority of 2, when inserted into the priority queue, it should be inserted at the address 1000 The queue unit of , that is, after queue unit 1; for queue units with priority 3 and 4, when inserted into the priority queue, it should be inserted into the queue unit with address 1008, that is, after queue unit 2; for priority When the queue unit of 5 is inserted into the priority queue, it should also be inserted into the queue unit with address 1008, that is, after queue unit 2. This is because queue unit 3 has the highest priority, so the queue unit with priority 5 All new queue units should be inserted between queue unit 3 and queue unit 2, that is, after queue unit 2.

1 2 3 4 5 empty address 1000 1008 1008 1008

Table I

Please refer to FIG. 2 . FIG. 2 is a flow chart of inserting queue units in the priority queue management method provided by the present invention.

Step 201, constructing a queue unit based on a new message.

Since the priority queue is used in the processing of messages with priority, when a new message requests processing, it is necessary to construct a queue unit for this message and insert the queue unit into the priority queue.

When constructing a queue unit based on a new message, the message pointer data item in the queue unit is equal to the storage address of the new message; the priority data item of the queue unit is equal to the priority of the new message; the forward pointer and the backward pointer of the queue unit are both empty address.

Step 202, judging whether the priority of the new queue unit is the highest priority, if yes, execute step 210, otherwise execute step 203.

The highest priority here is equal to the number of priorities that the priority queue can handle.

In step 203, the priority of the new queue unit plus 1 is used as the current index number.

Step 204, read the element whose index number is the current index number from the index table of the queue description, and use it as the current element.

Step 205, judging whether the value of the current element is an empty address, if yes, go to step 206, otherwise go to step 209.

Step 206, modify the value of the current element to the address of the new queue unit. That is to say, after this insertion operation is completed, the queue unit whose priority is equal to the current index number should be inserted after the queue unit inserted this time.

Step 207, judging whether the value of the current index number is equal to the highest priority, if yes, go to step 210, otherwise go to step 208.

In step 208, add 1 to the value of the current index number as a new current index number, and return to step 204 for execution.

This step is equivalent to preparing to process the next element in the index table.

Step 209 , judging whether the value of the current element is equal to the value of the element whose index number is the priority of the new queue unit, if yes, execute step 206 , otherwise execute step 210 .

Step 210, according to the priority of the new queue unit, determine the insertion position from the index table, and insert the new queue unit based on the new message into the priority queue.

According to the description of the priority queue shown in Figure 1, the value of each element in the index table indicates that the new queue unit whose message priority data item is equal to the element index number, when inserted into the priority queue, should be inserted into the following The value of this element is the address of the queue unit following. If the value of an element is a null pointer, it means that the new queue unit whose message priority data item is equal to the index number of this element should be inserted at the head of the queue when it is inserted into the priority queue.

Therefore, take the priority of the new queue unit as the index number, and read the value of the element corresponding to the index number in the index table, which is the storage address of the forward queue unit when the new queue unit is inserted into the priority queue. Further, by the value of the backward pointer data item of the forward queue unit, the storage address of the backward queue unit when the new queue unit is inserted into the priority queue can be obtained; if the address value of the forward queue unit obtained from the index table If it is an empty address, then the new queue unit should be inserted into the queue head of the priority queue.

Inserting a queue unit into a priority queue is actually inserting a unit into a doubly linked list. The purpose of the present invention is to quickly locate the insertion position, and for the steps of how to insert, the present invention is the same as the prior art.

Step 211, end.

Taking the priority queue shown in Figure 1 as an example, if a new queue unit 4 has a priority of 4 and an address of 1020, then after this queue unit is inserted into the priority queue, the index table shown in Table 1 corresponds to changed as shown in Table 2.

1 2 3 4 5 empty address 1000 1008 1008 1020

Table II

That is to say, before this insertion operation, the queue unit with priority 5 should be inserted into the queue unit with address 1008, that is, after queue unit 2 shown in Figure 1; after this insertion operation, the priority is 5 The queue unit should be inserted after the queue unit 4 whose priority is 4 and whose address is 1020.

If there is a new queue unit 5 with a priority of 1 and an address of 1030, after this queue unit is inserted into the priority queue, the index table is shown in Table 3.

1 2 3 4 5 empty address 1000 1008 1008 1020

Table three

Table 3 is unchanged from Table 2. This is because the newly inserted queue unit is inserted at the head of the queue. Before and after this insertion operation, the queue unit with priority 2 should be inserted into the queue unit with address 1000, that is, 1 after queue unit 1 shown.

If there is a new queue unit 6 with a priority of 3 and an address of 1028, then after this queue unit is inserted into the priority queue, the index table shown in Table 3 becomes correspondingly shown in Table 4.

1 2 3 4 5 empty address 1000 1008 1028 1020

Table four

That is to say, before this insertion operation, the queue unit with priority 4 should be inserted into the queue unit with address 1008, that is, after queue unit 2 shown in Figure 1; after this insertion operation, the priority is 4 The queue unit should be inserted after the queue unit 4 whose priority is 3 and whose address is 1028.

The priority queue after these several insertion operations is shown in Figure 3.

Please refer to FIG. 4 , which is a flow chart of deleting a queue unit in the priority queue management method provided by the present invention.

For a priority queue, the queue unit at the end of the queue has the highest priority and is the first to enter the queue among queue units of the same priority. Therefore, the message processing module starts from the tail of the priority queue each time, processes the messages encapsulated by the queue unit one by one, and needs to delete the queue unit from the queue, and then modify the index table accordingly.

Step 401, perform subsequent processing on the message encapsulated by the queue unit at the end of the queue.

Step 402 , judging whether the value of the element whose index number is equal to the highest priority in the index table is an empty address, if yes, execute step 408 , otherwise execute step 403 .

In step 403, the priority of the queue unit at the end of the queue plus 1 is used as the current index number.

Step 404, assigning the value of the forward pointer data item in the queue unit at the end of the queue to the element whose index number is the current index number in the index table.

Step 405, judge whether the current index number is equal to the highest priority, if yes, execute step 407, otherwise execute step 406.

Step 406, adding 1 to the value of the current index number as the current index number.

This step is equivalent to preparing to process the next element in the index table.

Step 407, delete the queue unit located at the end of the queue from the priority queue, and end this processing flow.

Deleting a queue unit from the priority queue is actually deleting a unit from the tail of the doubly linked list. For the steps of how to delete, the present invention is the same as the prior art.

Step 408, the priority queue is an empty queue, and no queue unit can be deleted from it, and an error is reported.

According to the priority queue shown in FIG. 3 , before the queue unit is deleted, its corresponding index table structure is shown in Table 4.

After the queue unit 3 is deleted, the index table shown in Table 4 becomes correspondingly shown in Table 5.

1 2 3 4 5 empty address 1000 1008 1028 1020

Table five

After the queue unit 4 is deleted, the index table shown in Table 5 becomes correspondingly shown in Table 6.

1 2 3 4 5 empty address 1000 1008 1028 1028

Table six

After the queue unit 6 is deleted, the index table shown in Table 6 becomes correspondingly shown in Table 7.

1 2 3 4 5 empty address 1000 1008 1008 1008

Table seven

After the queue unit 2 is deleted, the index table shown in Table 7 becomes correspondingly shown in Table 8.

1 2 3 4 5 empty address 1000 1000 1000 1000

table eight

After deleting queue unit 1, the index table shown in Table 8 becomes correspondingly shown in Table 9.

1 2 3 4 5 empty address 1030 1030 1030 1030

Table nine

After the queue unit 5 is deleted, the priority queue is an empty queue, and the index table shown in Table 9 becomes correspondingly as shown in Table 10.

1 2 3 4 5 empty address empty address empty address empty address empty address

table ten

It should be noted that, in practical applications, insertion and deletion of queue units are often performed randomly and alternately. However, this does not affect the effectiveness of the priority queue management method provided by the present invention in improving the processing speed when the queue unit is inserted into the priority queue.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the protection scope of the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (6)

1, a kind of management method of priority query, it is characterized in that, the concordance list that comprises different priorities queue unit insertion position for each priority query's configuration, and all insertion positions in the concordance list are initialized as address blank, when new queue unit was inserted into priority query, this method also comprised:

Steps A according to the priority of new queue unit and the insertion position information in the concordance list, is determined the insertion position of described new queue unit, and according to determined insertion position new queue unit is inserted in the priority query;

Step B refreshes the insertion position in the concordance list;

Step B comprises:

Step B1 judges whether the priority of new queue unit is limit priority;

Step B2, if when the priority of new queue unit is not limit priority, adding 1 with the priority of new queue unit is the current cable quotation marks;

Step B3 reads the insertion position of current cable quotation marks correspondence in the concordance list, and judges whether to need to revise the insertion position of being read;

Step B4 when revising the insertion position of being read as if needs, is revised as the address of new queue unit with the insertion position of current cable quotation marks correspondence, and judges whether the current cable quotation marks equal limit priority;

Step B5, if the current cable quotation marks are not equal to limit priority, this adds 1 back as new current cable quotation marks with the current cable quotation marks, returns execution in step B3.

2, the management method of priority query according to claim 1 is characterized in that, described in the steps A according to the priority of new queue unit and the insertion position that concordance list is determined described new queue unit is:

Priority with new queue unit is call number, with the insertion position of this call number correspondence in the concordance list as new queue unit when being inserted into priority query, be positioned at the memory address of the queue unit before the new queue unit.

3, the management method of priority query according to claim 1 is characterized in that, step B3 is described to judge whether that needing to revise the insertion position of being read is:

Judge whether the pairing insertion position of current index equals insertion address any one among both of address blank or described new queue unit,, otherwise think and do not need to revise the insertion position of being read if then think and need to revise the insertion position of being read.

4, the management method of priority query according to claim 1 is characterized in that, this method further comprises:

Step C, the queue unit that will be arranged in rear of queue is deleted from priority query, and refreshes the insertion position of concordance list.

5, the management method of priority query according to claim 4 is characterized in that, described step C comprises:

Step C1 judges in the concordance list with limit priority whether be address blank as the pairing insertion position of call number, if execution in step C6 then, otherwise the queue unit that will be arranged in rear of queue deletes from priority query, and execution in step C2;

Step C2 adds 1 as the current cable quotation marks with the priority of the queue unit of deleting among the step C1;

Step C3, with the value of forwarding pointer data item in the queue unit of deleting among the step C1, give the insertion position of current cable quotation marks correspondence in the concordance list, judge then whether the value of current cable quotation marks equals limit priority, if execution in step C5 then, otherwise execution in step C4;

Step C4 adds 1 back as new current cable quotation marks with the value of current cable quotation marks, returns execution in step C3;

Step C5, the queue unit that will be arranged in rear of queue is deleted from priority query, finishes this treatment scheme;

Step C6 determines that priority query is empty queue, can't be from wherein deleting any queue unit.

According to the management method of claim 4 or 5 described priority queries, it is characterized in that 6, the described queue unit that will be arranged in rear of queue from priority query's deletion is:

With the value of the forwarding pointer data field of deleted queue unit, give describe with the priority query corresponding queues in formation tail pointer data field; Value with the forwarding pointer data field of deleted queue unit is the address, and address blank is revised as in the consequent pointer data territory that is stored in the queue unit at this place, address.

Images