以下は、HaskellでParing Heapを実装した例です。この実装では、要素の型を a として、最小値を表すために Ord a を使っています。

ParingHeap.hs

data PHeap a = Empty | Node a [PHeap a]

mergePairs :: Ord a => [PHeap a] -> PHeap a
mergePairs [] = Empty
mergePairs [h] = h
mergePairs (h1:h2:hs) = merge (merge h1 h2) (mergePairs hs)

merge :: Ord a => PHeap a -> PHeap a -> PHeap a
merge h Empty = h
merge Empty h = h
merge h1@(Node x1 hs1) h2@(Node x2 hs2)
  | x1 < x2   = Node x1 (h2:hs1)
  | otherwise = Node x2 (h1:hs2)

insert :: Ord a => a -> PHeap a -> PHeap a
insert x = merge (Node x [])

findMin :: Ord a => PHeap a -> Maybe a
findMin Empty = Nothing
findMin (Node x _) = Just x

deleteMin :: Ord a => PHeap a -> Maybe (PHeap a)
deleteMin Empty = Nothing
deleteMin (Node _ hs) = Just $ mergePairs hs

この実装では、PHeapは、空のヒープ Empty またはノードを表す Node a [PHeap a] として定義されています。 mergePairs関数は、PHeapのリストを取り、それらをマージするためにmerge関数を使用して、新しいヒープを作成します。 insert関数は、要素をヒープに挿入するためにmerge関数を使用します。 findMin関数は、最小値を見つけるために、最初のノードの値を返します。 deleteMin関数は、最小値を削除し、新しいヒープを作成するためにmergePairs関数を使用します。

なお、この実装は永続的なデータ構造としては実装されていません。

ParingHeapの各操作、挿入、削除、最小値の取得の償却計算量を教えてください

Paring Heapの各操作の償却計算量は、以下の通りです。

挿入（insert）：O(1)の償却計算量

insert操作では、新しい要素をノードとして作成し、空のヒープとマージするだけなので、常に O(1) の償却計算量です。
最小値の取得（findMin）：O(1)の償却計算量

findMin操作では、ヒープの最小値は常にルートノードにあり、O(1)で取得できます。
削除（deleteMin）：O(log n)の償却計算量

deleteMin操作では、最小値を削除した後、子ノードをペアリングして新しいヒープを作成する必要があります。この際にペアリングの回数は、削除後のノード数をnとすると、最大でlog n回となります。ペアリングは、一度に2つのノードをマージすることができるので、各ペアリングの計算量はO(1)です。従って、deleteMin操作の償却計算量はO(log n)です。
Paring Heapの挿入と最小値の取得は非常に高速で、平均的な場合でもO(log n)の償却計算量を持つバイナリヒープよりも優れています。ただし、Paring Heapのペアリングによる削除操作は、バイナリヒープのような木の再構築よりも遅い可能性があるため、一部の応用では実用的でない場合があります。