**Section:** 27.8.8 [alg.heap.operations] **Status:** C++17
**Submitter:** Peter Sommerlad **Opened:** 2012-07-09 **Last modified:** 2017-07-30 20:15:43 UTC

**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 27.8.8 [alg.heap.operations]:

-1- A

heapis a particular organization of elements in a range between two random access iterators[a,b). Its two key properties are:

- There is no element greater than
*ain the range and*amay be removed bypop_heap(), or a new element added bypush_heap(), in O(log(N)) time.

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

*ais 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, fori>=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 are~~such that:(1.1) --

~~There is no element greater than~~*ain the range and

For alli >= 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) --

*amay be removed bypop_heap(), or a new element added bypush_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.

Change 27.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 are~~such that:(1.1) —

~~There is no element greater than~~With $N=\mathtt{b}-\mathtt{a}$, for all $i$, $0<i<N$,`*a`in the range and`comp(a[`

$\lfloor \genfrac{}{}{0.1ex}{}{i-1}{2}\rfloor $`], 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`

.](1.2) —

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