Created
March 24, 2023 08:50
-
-
Save cm-kazup0n/255a3acb5a1562138766507ceb2fc247 to your computer and use it in GitHub Desktop.
以下は、HaskellでParing Heapを実装した例です。この実装では、要素の型を a として、最小値を表すために Ord a を使っています。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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のペアリングによる削除操作は、バイナリヒープのような木の再構築よりも遅い可能性があるため、一部の応用では実用的でない場合があります。