Pairing Heap

Introduction

A pairing heap is a data structure that supports insertion, querying or deleting the minimum, melding, and changing element values. It is a meldable heap. It is fast and structurally simple, but because its amortized complexity is based on potential analysis, it cannot be made persistent.

Definition

A pairing heap is a weighted multiway tree satisfying the heap property (as shown below): the weight of each node is less than or equal to that of all its children (using a min-heap as the example below).

We usually store a pairing heap using the child-sibling representation (as shown below). All children of a node form a singly linked list. Each node stores a pointer to its first child, that is, the head of the list, and a pointer to its right sibling.

This representation makes pairing heaps easy to implement and also makes complexity analysis convenient.

struct Node {
  T v;  // T is the weight type
  Node *child, *sibling;
  // child points to this node's first child, and sibling points to this node's next sibling.
  // If this node has no child or next sibling, the pointer points to nullptr.
};

It follows from the definition that, compared with other common heap structures, a pairing heap maintains no extra information such as tree size, depth, or rank (a binary heap also maintains no extra information, but it guarantees the complexity of its operations by maintaining a strict complete-binary-tree structure). Moreover, any tree satisfying the heap property is a valid pairing heap. This simple and highly flexible data structure is the foundation of pairing heaps' excellent practical efficiency; in contrast, the poor constants of Fibonacci heaps are precisely due to their need to maintain a great deal of extra information.

A pairing heap guarantees its total complexity through a carefully designed order of operations. The original paper¹ called it “a Self Adjusting Heap”. In this respect it is quite similar to a Splay tree (called a “Self Adjusting Binary Tree” in the original paper).

Operations

Querying the minimum

From the definition of a pairing heap, the root node must have the minimum weight, so we can return the root node directly.

Melding

Melding two pairing heaps is simple: first make the smaller of the two root nodes the new root, then insert the larger root as its child (see the figure below).

Note that a node's child list is ordered by insertion time: the rightmost node became a child of the parent earliest, while the leftmost node became a child of the parent most recently.

Node* meld(Node* x, Node* y) {
  // If either heap is empty, return the other directly
  if (x == nullptr) return y;
  if (y == nullptr) return x;
  if (x->v > y->v) std::swap(x, y);  // After the swap, x is the heap with the smaller weight, and y is the one with the larger weight
  // Make y a child of x
  y->sibling = x->child;
  x->child = y;
  return x;  // The new root is x
}

Insertion

Now that we have melding, insertion is simply a matter of treating the new element as a new pairing heap and melding it with the original heap.

Deleting the minimum

First, it is worth noting that the operations above are very lazy: they do not maintain the data structure at all. We therefore need to design deletion of the minimum carefully to ensure that the total complexity remains bounded.

The root is the minimum, so it is the node to delete. What happens after removing the root? All of the root's former children form a forest, while a pairing heap should be a tree. We therefore need to merge all of these children in some order.

A natural idea is to use the meld function to merge the children one by one from left to right. This is clearly correct, but it causes the complexity of a single operation to degenerate to $O(n)$.

To guarantee the total amortized complexity, we need to use a “two-step” melding method:

1. Pair the children, and use meld to merge the two children in each pair (see figure 1).
2. Merge the newly produced heaps one by one from right to left (that is, from the older children toward the newer children; see figure 2).

First implement a helper function merges, which merges all siblings of a node.

Node* merges(Node* x) {
  if (x == nullptr || x->sibling == nullptr)
    return x;  // If the tree is empty or has no next sibling, no merge is needed; return.
  Node* y = x->sibling;                // y is x's next sibling
  Node* c = y->sibling;                // c is the sibling after the next one
  x->sibling = y->sibling = nullptr;   // Detach them
  return meld(merges(c), meld(x, y));  // The core step
}

The last line is the core of this function and has three parts:

1. meld(x,y) “pairs” x and y.
2. merges(c) recursively merges c and its siblings.
3. Merge the two new trees produced by the two operations above.

Note that the direction of the merge in the second step is important (from right to left). The recursive implementation above guarantees this order. If you implement an iterative version yourself, be sure to preserve the order; otherwise the complexity guarantee will be lost.

With the merges function, the delete-min operation is immediate.

Node* delete_min(Node* x) {
  Node* t = merges(x->child);
  delete x;  // Reclaim memory if necessary
  return t;
}

Decreasing an element's value

To implement this operation, add a “parent” pointer to each node. When a node has a left sibling, this pointer points to the left sibling rather than the actual parent; otherwise, it points to its parent.

First, change the node definition to:

struct Node {
  LL v;
  int id;
  Node *child, *sibling;
  Node *father;  // Added: parent pointer; if this node is the root, it points to the null pointer nullptr
};

Modify the meld operation as follows:

Node* meld(Node* x, Node* y) {
  if (x == nullptr) return y;
  if (y == nullptr) return x;
  if (x->v > y->v) std::swap(x, y);
  if (x->child != nullptr) {  // Added: maintain the parent pointer
    x->child->father = y;
  }
  y->sibling = x->child;
  y->father = x;  // Added: maintain the parent pointer
  x->child = y;
  return x;
}

Modify the merges operation as follows:

Node *merges(Node *x) {
  if (x == nullptr) return nullptr;
  x->father = nullptr;  // Added: maintain the parent pointer
  if (x->sibling == nullptr) return x;
  Node *y = x->sibling, *c = y->sibling;
  y->father = nullptr;  // Added: maintain the parent pointer
  x->sibling = y->sibling = nullptr;
  return meld(merges(c), meld(x, y));
}

Now let us consider how to implement the decrease-key operation.
First, we observe that after decreasing the weight of node x, the subtree rooted at x still satisfies the pairing-heap property, but the heap property may no longer hold between x and x's parent.
Therefore, we cut out the entire subtree rooted at x. Both resulting trees now satisfy the pairing-heap property, and melding them completes the operation.

// root is the heap root, x is the node to operate on, and v is the new weight; v <= x->v must hold when called
// Return the new root node
Node *decrease_key(Node *root, Node *x, LL v) {
  x->v = v;                 // Update the weight
  if (x == root) return x;  // If x is the root, return directly
  // Cut x out of fa's children; the case depends on x's position.
  if (x->father->child == x) {
    x->father->child = x->sibling;
  } else {
    x->father->sibling = x->sibling;
  }
  if (x->sibling != nullptr) {
    x->sibling->father = x->father;
  }
  x->sibling = nullptr;
  x->father = nullptr;
  return meld(root, x);  // Meld x and the root again
}

Complexity Analysis

The structure and implementation of a pairing heap are simple, but its time-complexity analysis is not easy.

The original paper¹ analyzed only that meld and delete-min both have amortized complexity $O(\log n)$, while conjecturing that all of its operations have the same complexity as those of a Fibonacci heap.

Unfortunately, it was later discovered that for a pairing heap maintaining no extra information, under certain operation sequences the amortized lower bound for the decrease-key operation is at least $\Omega (\log \log n)$².

Currently, some of the better estimates for the upper bounds are Iacono's $O(1)$ meld and $O(\log n)$ decrease-key³, and Pettie's $O(2^{2 \sqrt{\log \log n}})$ meld and decrease-key⁴. Note that all of the complexities mentioned above are amortized, so the minimum of the individual results cannot be taken separately.

References

• https://en.wikipedia.org/wiki/Pairing_heap
• https://brilliant.org/wiki/pairing-heap/