与total-order相比,partial-order是否足以构建堆？

Question

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.

Answer 1

要求priority_queue是比较器定义严格的弱排序(C++标准的第23.6.4节).后者在§25.4/ 4中定义如下:

术语"严格"是指对所有x的反自由关系的要求(!comp(x,x)),对于要求的要求不弱于总排序的要求,但强于部分排序的要求.如果我们将equiv(a,b)定义为!comp(a,b)&&!comp(b,a),则要求comp和equiv都是传递关系:

- comp(a,b)&& comp(b,c)意味着comp(a,c)

- equiv(a,b)&& equiv(b,c)意味着equiv(a,c)[注意:在这些条件下,可以证明

i)equiv是等价关系

ii)comp引起由等价确定的等价类的明确定义的关系

iii)诱导关系是严格的总排序. - 结束说明]

换句话说,比较器定义的关系不必是总的,但它必须是相对于假设关系定义的等价类的总和equiv,它将所有元素定义为相等且不小于或大于每个其他.

换句话说,比较关系未涵盖的任何元素都将被视为相等.