Data Structure: Application of Priority Queue

Here is an important sketch of data structures "priority queue". I am not teaching, but I hope to provide a thinking of similar problems. Therefore, learning is for learning, rather than practical, and involving more Nouns concept or terminology, for books that don't understand the data structure, this will not be introduced here. ^^

Priority Queue is a collection-based abstract data type, each element has a priority, 1) lookup; 2) Insert a new element; 3) Delete. In the minimum priority queue (Min Priority Queue), find the user's minimum element, delete the operation to delete the element; for the maximum queue (Max priority queue), find the operation to search for the largest element , Delete the operation to delete the element. The elements in the priority queue can have the same priority, and the lookup and deletion operation can be performed according to any priority.

The data structure implementation of the priority queue has many kinds: unordered linked table, ordered latter table, two fork search tree, left height, priority tree, etc. The priority tree satisfies the following two properties:

1) There is only one element in each node in the tree.

2) The value of any of the nodes in the tree is higher than the value of the elements stored in its son node.

In particular, when a priority tree is approximately bifurcous, we call it a bunch of or sequenced trees. For example, the sequencing is done with this data structure (priority queue), the priority is the value of the data to be riged. .

The following five specific examples illustrate the application of the priority queue in the problem.

(1) The priority queue data structure that is often used in the job scheduling algorithm, first lifting "short homework priority scheduling" as an example:

Under normal circumstances, we hope that the time consuming will be completed as soon as possible, that is, short homework is preferred to consume some time. Make short homework, no one of the methods of locking long homework is for each The job allocates a priority. Allocation priority formula is 100 * (Tused (x) -tinit (x)), Tused () is the time consumption of the job, Tinit () is the time arrival time. 100 is a need to need The number of adjustments is usually equal to the total number of jobs. One job can be represented by a structure consisting of job identifiers and job priorities, namely:

Struct Processtype {

Int ID;

Int priority;

}

In order to schedule time, the type of ProcesstYPE WAITING is set in the time-time system. Procedure initial () and select () are processed. Whenever a new job arrives, process initial () will this The job is inserted into the priority queue Waiting. When the system has time to use, select () selects a higher priority to the highest job and remove the job from waiting, and temporarily store the job record. In order to complete the time period, bring back a new priority to re-entry. Here, there is a deletemin () function returns a pointer to the highest priority job, and currentTime () is a function that is used, and execute () is processing The process of homework. The framework implemented by the algorithm will be given below.

Void Initial (int P) // P is the job number

{

PROCESSSSTYPE process;

Process.id = P;

Process.priority = -currenttime (); //

INSERT (Process, Waiting); / / / / to the newly reached the job into the priority queue

}

void select ()

{

Int begintime, endtime;

PROCESSSSTYPE process;

Process = (deletemin) -> Element; // Select the highest priority job and get out of the team

Begintime = CurrentTime ();

Execute (Process.id); // Job Turnover Run

EndTime = CURRENTTIME ();

Process.Priority = 100 * (endtime-begintime); // Reassign Priority

INSERT (Process, Waiting); // Process Bring back new priority re-entry}

(2) Using the stack of priority queues to complete the sequencing, you can think that the priority is the value of the data to be arranged:

Void Pushdown_Minheap (int first, int last)

{// Complete the function of building the minimum stack

Long i, j, x;

i = first;

J = i * 2;

X = data [i];

While (j <= last) {

IF (J

J ;

IF (x

Data [i] = data [j];

i = j;

J = 2 * i;

}

Else

Break;

}

Data [i] = x;

}

Void MinHeapsort (int first, int last) // The following is an abstract stacking algorithm

{// If l is a non-empty table, the mark * step can be used to complete the initialization directly

For (all elements in Table L) Do INSERT (x, s); // *

While (Not Empty (s)) {

Y = deletemin (s);

Output Y;

}

} / * Stack specific implementation see http://expert.9cbs.net/expert/topic/2059/2059607.xml?temp =.8768579 * /

(3) Priority queue can get a good application in many "greedy algorithms", this is worth noting. For example, the coding rule of the Huffman tree has the nature of "greedy choice". Assume that the priority queue is used in INSERT () and DELETEMIN () 2 basic operations, using a pile of data structures, abstract algorithm implementation process is as follows:

PriorityQueueType * huffuman (priorityQueueType * s) // Build a Huffman Code Tree

{// If l is a non-empty table, the mark * step can be used to complete the initialization directly

For (all elements in Table L) Do INSERT (x, s); // *

For (int i = 0; i

x = deletemin (s); // Take two of the two minimum signs

Y = deletemin (s);

PriorityQueueType * t = new ;

Maketree (x, y, t); // combines nodes x, y into a tree with node T is the root.

T.PRIORITY = X.Priority Y.Priority;

INSERT (t, s); // Put the root tree T, reinstate the priority queue

} Once the cycle is over, there are only 1 node left in the priority queue S.

Return getmin (s) // Returns the node of the minimum right of the priority queue S, ie Huffman tree root

}

(4) Machine scheduling problem: Investigate a mechanical factory, which is one of the same machines. The existing N jobs need to be handled, the processing time of the job I is Ti, this time is from the time to put the job into the machine until the job is removed from the machine. The so-called scheduling (S C HE E D U) is partitioning the job according to the operation time of the operation in the machine, making:

• A machine can only handle one job in the same time.

• A job cannot be processed on both machines at the same time.

• Once the Job i is run, TI timing is required.

Our mission is to write a program to determine how to schedule the shortest processing time required to perform a given N jobs on the M machine.

The scheduling problem is one of the famous NP-complex issues (NP represents Nondeterministic Polynornial). NP- Complex and NP-full problems are issues that have not found a multi-term time complexity algorithm. Such problems usually need to use an approximation algorithm to solve. In scheduling issues, a simple scheduling policy called longest processing time priority (LONGEST Processing Time First, LPT) is used, which can help us get an ideal scheduling length. This length is 4 / 3-1 / (3 * m) of the optimal scheduling length. In the LPT algorithm, the job is arranged in the order of decrementing the time required. When assigning a job, it always assigns it to the first machine that is first changed. Theorem: f * (i) is the optimal scheduling completion time of the job set I on the M machine, F (i) is the scheduling completion time obtained by the LPT scheduling policy, (f (i) / f * ( I)) <= 4/3 - 1 / (3 * m).

In fact, LPT scheduling is more close to the best solution than the above-mentioned boundary. It is obvious that LPT scheduling has a nature of a greed, accordingly, we can use the priority queue to solve it. That is The completion time t [n] is sorted in descending sequencing is the sequence of job scheduling. The algorithm is to use the heap structure to achieve the order of the priority queue, that is, the heap sort.

(5) Packing Problem: The N item is provided, the volume of each item is S1, S2, .., SN, and 0 1 && j <= m) J ; // Looking for the first to accommodate the item S [T The JU only box, preferred to put the box if (j> M) Return False; //m only the box is accommodated without this N item B [J] <- B [J] ∪ {T}; // T item storage In the box, add a collection B [J] record B [J] = S [T];} OUTPUT (B [1], B [2], ... B [M]) Return True;} Easy It is proven that the time efficiency of the above NIFF algorithm is O (n ^ 2), which is an algorithm for a multi-item boundary. The data structure of the above priority queue S is just a simple ordered array. Summary: The above is mainly introduced in the data structure Priority Queue "In some typical problems. In" Priority Queue ", it is preferred to indicate that" service "is not in the order of queuing, but provides services in the priority order of each object. This nature is very suitable Some algorithms with greed selection (as data structures that implement the algorithm), this is also the center of gravity to explain the above problems.

It is particularly pointed that the algorithm is not dependent on the specific computer language, which mostly uses the abstract algorithm model to describe the problem of solving problems, and also uses the amount of abstract data type to describe the tool, the above practice is for convenient description. The principle of algorithm is not confident. It is clear that the different computer languages ​​can achieve the same algorithm, but implement some algorithm can not only use different abstract data types, but also select the appropriate specific implementation for the abstract data type. means.

Finally, it is also important to note that the above focus more focuses on the application or ideas of this abstract data type in solving the algorithm used by a certain problem. There is no specific implementation code for the priority queue in the article. Because of its implementation, there are also different efficiency of different situations. If you need, please check the reference book, because the books of the data structure are more detailed, much more detailed, I will not Multi-narrative. :)