A binary heap is a complete binary tree where each node holds a value and satisfies the heap-order property: for every node, its value is no greater (in a min-heapp) or no smaller (in a max-heap) than those of its children. The C++ Standard Library provides std::priority_queue, which implements a binary heap by default — a max-heap unless a custom comparator is supplied. This section focuses on the min-heap variant; equivalent behavior for max-heaps follows via comparator inversion. #### Core Operations

A binary heap supports three fundamental operations in O(log n) time: - Top query: Retrieve the minimum element.

• Extract-min: Remove and return the smallest element.
• Insert: Add a new element while preserving heap structure.

Implementation Strategy

Two invariants must be maintained: 1. Shape property: The tree remains a complete binary tree (all levels filled left-to-right). 2. Order property: Every parent is ≤ its children (min-heap).

• Top query: Since the root always holds the minimum, accessing heap[1] (1-indexed array representation) suffices.
• Extract-min: Swap the root with the last leaf, reduce size, then "bubble down" the new root: repeatedly exchange it with its smaller child until order is restored.
• Insert: Append the new element at the next available leaf position, then "bubble up" by swapping with its parent while violating the order property.

void push(int x) {
    data.push_back(x);
    int i = data.size() - 1;
    while (i > 0 && data[(i - 1) / 2] > data[i]) {
        std::swap(data[(i - 1) / 2], data[i]);
        i = (i - 1) / 2;
    }
}

void pop() {
    if (data.empty()) return;
    std::swap(data[0], data.back());
    data.pop_back();
    int i = 0;
    while (true) {
        int left = 2 * i + 1, right = 2 * i + 2;
        int smallest = i;
        if (left < data.size() && data[left] < data[smallest])
            smallest = left;
        if (right < data.size() && data[right] < data[smallest])
            smallest = right;
        if (smallest == i) break;
        std::swap(data[i], data[smallest]);
        i = smallest;
    }
}

int top() const { return data.empty() ? -1 : data[0]; }
bool empty() const { return data.empty(); }

};

</details>### Leftist Tree (Mergeable Heap)

Unlike standard heaps, leftist trees support efficient merging (*O(log n)*) in addition to standard priority queue operations. They are self-balancing, heap-ordered binary trees governed by the *leftist property*. #### Key Definitions

- A *external node* is any node with fewer than two children (i.e., a leaf or a node with only one child).
- The *distance* (`dist`) of a node is the length (number of edges) of the shortest path from that node to an external node in its subtree. By convention, `dist(nullptr) = 0`.
- A leftist tree enforces: for every node, `dist(left_child) ≥ dist(right_child)`.

This bias toward left-heavy structure ensures logarithmic merge depth. #### Merge Operation (`join`)

The core operation recursively merges two leftist trees: 1. If either tree is empty, return the other.
2. Ensure the root of the first tree holds the smaller key (swap if needed).
3. Recursively merge the right subtree of the first tree with the second tree.
4. Attach the result as the new right child.
5. Enforce the leftist property: if `dist(right) > dist(left)`, swap subtrees.
6. Update `dist`: `dist = dist(right_child) + 1`.

<details><summary>Minimal leftist tree with merge, insert, and extract-min</summary>```
struct LeftistNode {
    int val, dist;
    LeftistNode *left, *right;
    LeftistNode(int v) : val(v), dist(0), left(nullptr), right(nullptr) {}
};

LeftistNode* merge(LeftistNode* a, LeftistNode* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val > b->val) std::swap(a, b);
    a->right = merge(a->right, b);
    if (!a->left || a->right->dist > a->left->dist)
        std::swap(a->left, a->right);
    a->dist = a->right ? a->right->dist + 1 : 0;
    return a;
}

class LeftistHeap {
    LeftistNode* root = nullptr;
public:
    void push(int x) {
        root = merge(root, new LeftistNode(x));
    }

    int top() const { return root ? root->val : -1; }

    void pop() {
        if (!root) return;
        LeftistNode* old = root;
        root = merge(root->left, root->right);
        delete old;
    }

    bool empty() const { return !root; }
};

With pointer tracking and auxiliary bookkeeping, leftist trees can support: - Arbitrary deletion: Locate a node, detach it, merge its subtrees, and rebalance ancestors.

• Key update: Remove the node, modify its value, and reinsert it.
• Lazy erasure: Mark nodes invalid and skip them during extraction (common in competitive programming).

These extensions require storing node pointers externally (e.g., in an array indexed by ID) and implementing upward propagation to restore the leftist invariant after structural changes.