# positionMapping for last element in heap is not updated when extracting max element

MaxHeap.extractMax fails to update positionMapping for the last leaf moved to root when it ties its parent, corrupting heap indices and ordering.

- Payout: Contest reward
- Severity: medium
- Program: Collective
- Credited: MrPotatoMagic
- Disclosed: 2024-02-08
- Write-up quality: 7/10
- Original: https://github.com/code-423n4/2023-12-revolutionprotocol-findings/issues/363
- Library page: https://bugbountylibrary.com/r/c4%3A2023-12-revolutionprotocol%3AM-07
- Tags: domain:web3 impact:integrity kind:contest platform:code4rena sev:medium tech:solidity technique:source-review vuln:business-logic

**Target:** MaxHeap.sol Solidity max-heap data structure (extractMax/maxHeapify/updateValue)
**Root cause:** extractMax moves the last leaf to the root and calls maxHeapify, but maxHeapify returns early when the moved element ties its children, so positionMapping for that element is never updated from its old leaf index to 0.
**Steps:**
1. Heap state: itemIds 1..5 at indices 0..4 with values 50,20,15,10,20; itemId 2 (idx1) is parent of itemId 5 (idx4), both value 20.
2. Call `extractMax()`: popped=heap[0]=1, `heap[0]=heap[--size]` sets itemId 5 at index 0, size=4.
3. `maxHeapify(0)`: posValue=20, leftValue=20, rightValue=15; `posValue < leftValue || posValue < rightValue` is false, returns early; positionMapping[5] stays 4.
4. Call `insert(6,3)`: heap[4]=6, positionMapping[6]=4; now itemId 5 (root) and itemId 6 both map to index 4.
5. Call `updateValue(5,13)`: position=positionMapping[5]=4, oldValue=20; newValue<oldValue so `maxHeapify(4)` runs on itemId 6's subtree, returns early since 4>=size/2; root itemId 5 keeps value 13 below children 20 and 15.
6. Call `extractMax()`: pops itemId 5 (value 13) instead of itemId 2 (value 20), violating max-heap invariant.
**How found:** Code reading of extractMax/maxHeapify: noticed maxHeapify early-returns when the moved leaf ties its children, so the positionMapping write that normally happens in swap() never executes for the new root.
**Exploitation:** Admin-only functions; no direct attacker path shown. Demonstrated corruption of heap ordering causes wrong element extraction and stale/duplicate positionMapping entries, breaking protocol invariant.
**Insight:** When a heap stores an auxiliary index map, the root-replacement step in extractMax must update the moved leaf's index unconditionally before heapify; relying on swap() to fix indices misses the no-swap early-return path (ties or already-valid position).