Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
k=j m) break; if (k != m && heap[k] heap[k+1]) k++; if (heap[j] | 8.6 Determination ofEquivalence Classes 345 k j 1 if k m break if k m heap k heap k 1 k if heap j heap k break swap heap k heap k heap j heap j swap j k CITED REFERENCES AND FURTHER READING Sedgewick R. 1988 Algorithms 2nd ed. Reading MA Addison-Wesley pp. 126ff. 1 Knuth D.E. 1973 Sorting and Searching vol. 3 of The Art ofComputer Programming Reading MA Addison-Wesley . 8.6 Determination ofEquivalence Classes A number of techniques for sorting and searching relate to data structures whose details are beyond the scope of this book for example trees linked lists etc. These structures and their manipulations are the bread and butter of computer science as distinct from numerical analysis and there is no shortage of books on the subject. In working with experimental data we have found that one particular such manipulation namely the determination of equivalence classes arises sufficiently often to justify inclusion here. The problem is this There are N elements or data points or whatever numbered 1 . N. You are given pairwise information about whether elements are in the same equivalence class of sameness by whatever criterion happens to be of interest. For example you may have a list of facts like Element 3 and element 7 are in the same class element 19 and element 4 are in the same class element 7 and element 12 are in the same class . Alternatively you may have a procedure given the numbers of two elements j and k for deciding whether they are in the same class or different classes. Recall that an equivalence relation can be anything satisfying the RSTproperties reflexive symmetric transitive. This is compatible with any intuitive definition of sameness. The desired output is an assignment to each of the N elements of an equivalence class number such that two elements are in the same class if and only if they are assigned the same class number. Efficient algorithms work like this Let F j be the class or family number of element j. Start off with each element in its
