*This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.*

**Section:** 27.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 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
`*a`

in the range and`*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 are~~such 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.

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.