how to generate a barcode using asp.net c# A0 B in Software

Generating QR Code ISO/IEC18004 in Software A0 B

After union(A, D), union(B, E), union(C, F ):

After union(C, G), union(E, A):

After union(B, G):

Path compression With the data structure as presented so far, the total time for Kruskal s algorithm becomes O(|E| log |V |) for sorting the edges (remember, log |E| log |V |) plus another O(|E| log |V |) for the union and find operations that dominate the rest of the algorithm So there seems to be little incentive to make our data structure any more ef cient But what if the edges are given to us sorted Or if the weights are small (say, O(|E|)) so that sorting can be done in linear time Then the data structure part becomes the bottleneck, and it is useful to think about improving its performance beyond log n per operation As it turns out, the improved data structure is useful in many other applications But how can we perform union s and find s faster than log n The answer is, by being a 136

Figure 57 The effect of path compression: find(I) followed by find(K)

little more careful to maintain our data structure in good shape As any housekeeper knows, a little extra effort put into routine maintenance can pay off handsomely in the long run, by forestalling major calamities We have in mind a particular maintenance operation for our union- nd data structure, intended to keep the trees short during each find, when a series of parent pointers is followed up to the root of a tree, we will change all these pointers so that they point directly to the root (Figure 57) This path compression heuristic only slightly increases the time needed for a find and is easy to code function find(x) if x = (x) : (x) = find( (x)) return (x) The bene t of this simple alteration is long-term rather than instantaneous and thus necessitates a particular kind of analysis: we need to look at sequences of find and union operations, starting from an empty data structure, and determine the average time per operation This amortized cost turns out to be just barely more than O(1), down from the earlier O(log n) Think of the data structure as having a top level consisting of the root nodes, and below it, the insides of the trees There is a division of labor: find operations (with or without path 137

compression) only touch the insides of trees, whereas union s only look at the top level Thus path compression has no effect on union operations and leaves the top level unchanged We now know that the ranks of root nodes are unaltered, but what about nonroot nodes The key point here is that once a node ceases to be a root, it never resurfaces, and its rank is forever xed Therefore the ranks of all nodes are unchanged by path compression, even though these numbers can no longer be interpreted as tree heights In particular, properties 1 3 (from page 135) still hold If there are n elements, their rank values can range from 0 to log n by Property 3 Let s divide the nonzero part of this range into certain carefully chosen intervals, for reasons that will soon become clear: {1}, {2}, {3, 4}, {5, 6, , 16}, {17, 18, , 2 16 = 65536}, {65537, 65538, , 265536 }, Each group is of the form {k + 1, k + 2, , 2 k }, where k is a power of 2 The number of groups is log n, which is de ned to be the number of successive log operations that need to be applied to n to bring it down to 1 (or below 1) For instance, log 1000 = 4 since log log log log 1000 1 In practice there will just be the rst ve of the intervals shown; more are needed only if n 265536 , in other words never In a sequence of find operations, some may take longer than others We ll bound the overall running time using some creative accounting Speci cally, we will give each node a certain amount of pocket money, such that the total money doled out is at most n log n dollars We will then show that each find takes O(log n) steps, plus some additional amount of time that can be paid for using the pocket money of the nodes involved one dollar per unit of time Thus the overall time for m find s is O(m log n) plus at most O(n log n) In more detail, a node receives its allowance as soon as it ceases to be a root, at which point its rank is xed If this rank lies in the interval {k + 1, , 2 k }, the node receives 2k dollars By Property 3, the number of nodes with rank > k is bounded by n n n + + k 2k+1 2k+2 2 Therefore the total money given to nodes in this particular interval is at most n dollars, and since there are log n intervals, the total money disbursed to all nodes is n log n Now, the time taken by a speci c find is simply the number of pointers followed Consider the ascending rank values along this chain of nodes up to the root Nodes x on the chain fall into two categories: either the rank of (x) is in a higher interval than the rank of x, or else it lies in the same interval There are at most log n nodes of the rst type (do you see why ), so the work done on them takes O(log n) time The remaining nodes whose parents ranks are in the same interval as theirs have to pay a dollar out of their pocket money for their processing time This only works if the initial allowance of each node x is enough to cover all of its payments in the sequence of find operations Here s the crucial observation: each time x pays a dollar, its parent changes to one of higher rank Therefore, if x s rank lies in the interval {k + 1, , 2k }, it has to pay at most 2k dollars before its parent s rank is in a higher interval; whereupon it never has to pay again