相关疑难解决方法(0)

有大量的排序算法,但大多数只能在完全有序的集合上工作,因为他们认为任何两个元素都是可比较的.但是,是否有任何好的算法用于排序posets,其中一些元素是无法比较的？也就是说,由于从偏序集绘制的元素的集合S,什么是输出的最好方式排序X ₁,X ₂,...,X _ñ例如,如果X _我 ≤X _Ĵ,I≤J′

C++ std :: priority_queue只需要一个部分顺序.但如果它的实现是二进制堆,它是如何工作的？例如:假设我们有一个偏序集( {a, b, c, x}, {c < b, b < a, c < a} ),x具有无关a,b,c.那么最大堆是:

layer 1:    x
layer 2:  b   x
layer 3: x x a c

在弹出操作之后,以教科书中常见的方式,即用root替换root c并将大小减小1.然后我们需要在下面的树根下堆积树:

layer 1:    c
layer 2:  b   x
layer 3: x x a

我们会互换c,b因为c < b,不是吗？什么？从那以后我们仍然没有有效的堆b < a.但b不能"看" a.