进行部分顺序，而相比之下，总阶，足以建立一个堆？ [英] Is partial-order, in contrast to total-order, enough to build a heap?

问题描述

C ++的std :: priority_queue只需要一个偏序。但是，如果它的实施是一个二叉堆，它是如何工作的？ 例如：假设我们有一个偏序集（{A，B，C，X}，{C＆LT; B，B＆LT; A，C＆LT;一}）， X 无关与 A ， B ， C 。然后，最大堆是：

 图层1：X
第2层：宽x
第3层：X X是C
 

弹出操作后，在某种程度上常见于课本，即​​替换根ç和减1的大小。然后，我们需要heapify树下面，在根：

 图层1：C
第2层：宽x
层3：X X一
 

我们将交换 C 和 B 为 C＆LT; b ，不会吧？什么？我们还没有，因为 B℃的有效堆;一个。但 B 无法看到 A 。

解决方案

有关要求 priority_queue 是（C ++标准的§23.6.4），比较定义严格，弱序的。后者是在§25.4/ 4定义如下：

  

术语严格指漫反射的关系的要求（！排版（X，X）对于所有的x），并且术语弱到要求，这不象那些用于进行整体排序，但比那些更有力一个偏序。如果我们定义当量（A，B）作为补偿（A，B）及！＆安培; ！样稿（B，A），则要求是补偿和当量都为传递关系：

     

- 补偿（A，B）及和放大器;补偿（B，C）意味着补偿（A，C）

     

- 当量（A，B）及＆安培;当量（B，C）意味着当量（A，C）[注意：在这些条件下，它可以证明      

我）当量是一种等价关系

     

ⅱ）排版诱导由当量确定的等价类定义良好的关系

     

三）引起的关系是一个严格的全序。 - 注完]

在换句话说，比较器限定的关系，不必是总的，但它必须是总相对于由一个假想的关系所限定的等价类当量，系统其中所有的元素定义为等于是不小于或大于彼此

把它放在更简单的计算，不包括比较有关的任何元素都将被视为平等的。

C++ std::priority_queue just need a partial order. But if its implementation is a binary heap, how does it works? For example: assume we have a partially ordered set ( {a, b, c, x}, {c < b, b < a, c < a} ), x has nothing to do with a, b, c. Then a max-heap is:

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

After a pop operation, in a way commonly seen in text books, i.e. replace the root with c and decrease the size by 1. Then we need to heapify the tree below, at the root:

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

We will swap c and b as c < b, won't we? And what? We still don't have a valid heap since b < a. But b cannot "see" a.

解决方案

The requirement for priority_queue is (§23.6.4 of the C++ Standard) that the comparator defines a strict, weak ordering. The latter is defined in §25.4/4 as follows:

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

— comp(a, b) && comp(b, c) implies comp(a, c)

— equiv(a, b) && equiv(b, c) implies equiv(a, c) [ Note: Under these conditions, it can be shown that

i) equiv is an equivalence relation

ii) comp induces a well-defined relation on the equivalence classes determined by equiv

iii) The induced relation is a strict total ordering. — end note ]

In other words, the comparator-defined relation does not have to be total, but it must be total with respect to the equivalence classes defined by a hypothetical relation equiv, which defines all elements as equal that are not less-than or greater-than each other.

To put it in even simpler terms, any elements not covered by the comparator relation will be treated as equal.

这篇关于进行部分顺序，而相比之下，总阶，足以建立一个堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！