Proposed resolution:

This wording is relative to N4606.

1. Change [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.

[ 2016-08-03 Chicago LWG ]

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

Thurs PM: Moved to Tentatively Ready

[ 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 Chicago ]

Walter provided wording

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

Another similar issue to the operator< vs greater in nth_element but not as direct occurs in [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.