The following is the two fork heap implemented by the array, where max_size is the maximum length of the array; ElementType is the type of element; priority (x: elementtype) is a function, the return value is the priority of the element X, of course, can also be used in a priority To save the priority of each element (you should use an array in this typist issue to save the priority of each element, the priority in this question is the number of operations required to convert from the initial password to the password) .
Type priorityQueue = record contents: array [1..max_size] of elementtype; last: integer; end;
{Varint a priority queue} Procedure Makenull (var A: priorityQueue); begin a.last: = 0;
{Insert an element X} process (x: ElementTypeue) to the priority queue A; VAR i: integer; temp: elementtype; begin if a.last = max_size kilies error ('priority queue is full.' Else Begin a.last: = a.last 1; a.contents [a.last]: = x; i: = a.last; while (i> 1) and (priority (a.contents [i]) {Remove the priority of the priority of the priority queue, return it to} Function Deletemin: ElementType; Var minimun: ElementType; I: integer; begin if a.last = 0 Then Error (' Priority Queue Is Empty. ') Else Begin Minimun: = a.contents [1]; A.Contents [1]: = a.contents [a.last]; a.last: = a.last - 1; i: = 1; While i <(a.last Div 2) Do Begin if (Priority (a.contents [2 * i]) IF priority (a.contents [i])> priority (a.contents [j]) THEN becom temp: = a.contents [i]; a.contents [i]: = a.contents [j]; a.contents [J]: = Temp; I: = J; END ELSE begin {can not be pushed down} deletemin: = minimum; exit; end; end; {end of while} {This is already reaching the leaf node} deletemin: = minimum; EXI; {end of else} end; {end of deletemin} The complexity of the priority queue insertion and deletion element is O (LGN), so soon. The priority queue uses C as follows #define max_size 100 TypeDef int elementtype; // Defines the type of element, here it is assumed to be int type Struct priorityQueue {// Define Priority Queue ElementType Contents [Max_size]; int size;}; INT P [MAX_SIZE]; / / Return to the priority function value of element X, the better the higher the priority, the higher the int priority (const elementtype & x) {RETURN P [x]; / / usually use the array P to store the priority of each element in the actual application , // But actually calculate priority} with other methods (such as through formula) // Varges a priority queue Void Makenull (priorityQueue & q) {q.size = 0; / / Insert an element X in the priority queue Q Void INSERT (Const ElementType & X, PriorityQueue & q) {INT I; ElementType Temp; IF (q.size == max_size) {throw "priority queue is full.";} else {q.contents [q.size ] = x; i = q.size - 1; // Start while the last element ( (i> 0) && (Q.Contents [i]) } / / Delete the element of the priority function value of the priority queue, returns its value to ElementType deletemin (ElementType Result; Int i, J; IF (q.size == 0) {throw "priorityQueue & q";} else {result = q.contents [0]; q.contents [0] = q.contents [q.size - 1]; q.size- -; i = 0; while (2 * i 1 Return Result;} }
