2166. Heap property underspecified?

Section: 26.8.8 [alg.heap.operations] Status: C++17 Submitter: Peter Sommerlad Opened: 2012-07-09 Last modified: 2017-07-30

Priority: 3

View all other issues in [alg.heap.operations].

View all issues with C++17 status.

Discussion:

Another similar issue to the operator< vs greater in nth_element but not as direct occurs in 26.8.8 [alg.heap.operations]:

-1- A heap is a particular organization of elements in a range between two random access iterators [a,b). Its two key properties are:

  1. There is no element greater than *a in the range and
  2. *a may be removed by pop_heap(), or a new element added by push_heap(), in O(log(N)) time.

As noted by Richard Smith, it seems that the first bullet should read:

*a is not less than any element in the range

Even better the heap condition could be stated here directly, instead of leaving it unspecified, i.e.,

Each element at (a+2*i+1) and (a+2*i+2) is less than the element at (a+i), if those elements exist, for i>=0.

But may be that was may be intentional to allow other heap organizations?

See also follow-up discussion of c++std-lib-32780.

[2016-08 Chicago]

Walter provided wording

Tues PM: Alisdair & Billy(MS) to improve the wording.

[2016-08-02 Chicago LWG]

Walter provides initial Proposed Resolution. Alisdair objects to perceived complexity of the mathematical phrasing.

Previous resolution [SUPERSEDED]:

[Note to editor: As a drive-by editorial adjustment, please replace the current enumerated list format by the numbered bullet items shown below.]

Change [alg.heap.operations]:

1 A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties aresuch that:

(1.1) -- There is no element greater than *a in the range and
For all i >= 0,
comp(a[i], a[L]) is false whenever L = 2*i+1 < b-a,
and
comp(a[i], a[R]) is false whenever R = 2*i+2 < b-a.

(1.2) -- *a may be removed by pop_heap(), or a new element added by push_heap(), in O(log(N)) time.

[2016-08-03 Chicago LWG]

Walter and Billy O'Neal provide revised Proposed Resolution, superseding yesterday's.

Thurs PM: Moved to Tentatively Ready

Proposed resolution:

This wording is relative to N4606.

  1. Change 26.8.8 [alg.heap.operations] as indicated:

    Note to project editor: As a drive-by editorial adjustment, please replace the current enumerated list format by numbered bullet items.

    -1- A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties aresuch that:

    1. (1.1) — There is no element greater than *a in the range and With N=b- a, for all i, 0<i<N, comp(a[ ⌊ i - 1 2 ⌋ ], a[i]) is false.

      [Note to the project editor: In LaTeX the above insertion should be expressed as follows:

      With $N = b-a$, for all $i$, $0 < i < N$, comp(a[$\left \lfloor{\frac{i-1}{2}}\right \rfloor$], a[$i$]) is false.]

    2. (1.2) — *a may be removed by pop_heap(), or a new element added by push_heap(), in 𝒪(log(N)) time.