Skip to content

Pairing Heap

Introduction

A pairing heap is a data structure that supports operations such as insertion, querying/deleting the minimum, merging, and modifying elements. It is a type of mergeable heap. It has the advantages of high speed and simple structure, but due to its amortized complexity based on potential analysis, it cannot be made persistent.

Definition

A pairing heap is a weighted multiway tree that satisfies the heap property (as shown in the figure below), meaning each node's weight is less than or equal to all its children (taking a min-heap as an example, the same applies below).

Typically, we use the child-sibling representation to store a pairing heap (as shown in the figure below). All children of a node form a singly linked list. Each node stores a pointer to its first child (the head of the list) and a pointer to its right sibling.

This representation facilitates the implementation of pairing heaps and will also simplify complexity analysis.

1
2
3
4
5
6
struct Node {
  T v;  // T is the weight type
  Node *child, *sibling;
  // child points to the first child of this node, sibling points to the next sibling of this node.
  // If the node has no child/next sibling, the pointer points to nullptr.
};

From the definition, it can be observed that, compared to other common heap structures, pairing heaps do not maintain any additional information such as tree size, depth, or rank (binary heaps also do not maintain extra information, but they ensure operation complexity by maintaining a strict complete binary tree structure). Moreover, any tree satisfying the heap property is a valid pairing heap. This simple yet highly flexible data structure forms the basis for the excellent efficiency of pairing heaps in practice. In contrast, the poor constant factors of Fibonacci heaps are due to the need to maintain a lot of additional information.

Pairing heaps ensure their total complexity through a carefully designed sequence of operations. The original paper1 refers to it as a "Self Adjusting Heap." In this regard, it bears similarities to Splay trees (referred to as "Self Adjusting Binary Trees" in the original paper).

Process

Query Minimum

From the definition of a pairing heap, the root node's weight is always the smallest. Simply return the root node.

Merge

Merging two pairing heaps is straightforward. First, let the smaller of the two root nodes become the new root, then insert the larger root node as its child (see the figure below).

Note that a node's child list is sorted by insertion time, meaning the rightmost node became the parent's child earliest, and the leftmost node became the parent's child most recently.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Node* meld(Node* x, Node* y) {
  // If one is empty, directly return the other
  if (x == nullptr) return y;
  if (y == nullptr) return x;
  if (x->v > y->v) std::swap(x, y);  // After swap, x is the heap with smaller weight, y is the heap with larger weight
  // Set y as a child of x
  y->sibling = x->child;
  x->child = y;
  return x;  // The new root is x
}

Insert

Since we already have merge, insertion simply treats the new element as a new pairing heap and merges it with the original heap.

Delete Minimum

First, it should be noted that the above operations are quite lazy and do not maintain the data structure at all. Therefore, we need to carefully design the delete-minimum operation to ensure the total complexity does not become problematic.

The root node is the minimum, so we need to delete the root node. Consider what happens after removing the root: all original children of the root form a forest. However, a pairing heap should be a single tree, so we need to merge all these children in some order.

A natural idea is to use the meld function to merge the children from left to right one by one. While this approach is correct, it can degrade the single-operation complexity to \(O(n)\).

To ensure the total amortized complexity, a "two-step" merging method is used:

  1. Pair the children into pairs, using the meld operation to merge each pair of children together (see Figure 1 below).
  2. Merge the newly produced heaps from right to left (i.e., from the older children to the newer children) one by one (see Figure 2 below).

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

Implementation 
1
2
3
4
5
6
7
8
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 the next sibling of x
  Node* c = y->sibling;                // c is the next sibling after y
  x->sibling = y->sibling = nullptr;   // Disconnect
  return meld(merges(c), meld(x, y));  // Core part
}

The last sentence is the core of this function, which consists of 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 above two operations.

Note that the merging direction in the second step is required (from right to left). The recursive implementation of this function already ensures this order. If readers need to implement an iterative version, be sure to maintain this order; otherwise, the complexity guarantee will be lost.

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

Implementation 
1
2
3
4
5
Node* delete_min(Node* x) {
  Node* t = merges(x->child);
  delete x;  // If memory reclamation is needed
  return t;
}

Decrease Key

To implement this operation, we need to add a "parent" pointer to each node. When a node has a left sibling, it points to the left sibling instead of the actual parent; otherwise, it points to its parent.

First, modify the node definition as follows:

Implementation 
1
2
3
4
5
6
struct Node {
  LL v;
  int id;
  Node *child, *sibling;
  Node *father;  // New: parent pointer. If the node is the root, it points to nullptr.
};

Modify the meld operation as follows:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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) {  // New: maintain parent pointer
    x->child->father = y;
  }
  y->sibling = x->child;
  y->father = x;  // New: maintain parent pointer
  x->child = y;
  return x;
}

Modify the merges operation as follows:

Implementation 
1
2
3
4
5
6
7
8
9
Node *merges(Node *x) {
  if (x == nullptr) return nullptr;
  x->father = nullptr;  // New: maintain parent pointer
  if (x->sibling == nullptr) return x;
  Node *y = x->sibling, *c = y->sibling;
  y->father = nullptr;  // New: maintain parent pointer
  x->sibling = y->sibling = nullptr;
  return meld(merges(c), meld(x, y));
}

Now, let's 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's parent and x.
Therefore, we detach the entire subtree rooted at x. Now both trees satisfy the pairing heap property, and we merge them to complete the operation.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// root is the heap's root, x is the node to operate on, v is the new weight. It must be ensured that v <= x->v when calling.
// Returns the new root node.
Node *decrease_key(Node *root, Node *x, LL v) {
  x->v = v;                 // Update weight
  if (x == root) return x;  // If x is the root, return directly.
  // Detach x from fa's children. Here, we need to discuss 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);  // Re-merge x and the root node
}

Complexity Analysis

Pairing heaps have a simple structure and implementation, but their time complexity analysis is not straightforward.

The original paper1 only analyzed the complexity to show that meld and delete-min operations are amortized \(O(\log n)\), but conjectured that all operations have the same complexity as Fibonacci heaps.

Unfortunately, it was later discovered that pairing heaps without maintaining additional information have an amortized lower bound of at least \(\Omega (\log \log n)\) for the decrease-key operation under specific operation sequences2.

Currently, good estimates for the upper bounds include Iacono's \(O(1)\) meld and \(O(\log n)\) decrease-key3, and Pettie's \(O(2^{2 \sqrt{\log \log n}})\) for both meld and decrease-key4. Note that these complexities are amortized, so the minimum cannot be taken separately for each result.

References

  1. The pairing heap: a new form of self-adjusting heap ↩↩

  2. On the efficiency of pairing heaps and related data structures ↩

  3. Improved upper bounds for pairing heaps ↩

  4. Towards a Final Analysis of Pairing Heaps ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用