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.

### 2166. Heap property underspecified?

Section: 25.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 25.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 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.

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