ヒープソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
| クラス | ソート |
|---|---|
| データ構造 | 配列 |
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[1]（ヒープ領域とは無関係であることに注意する）。
アルゴリズムは、以下のように2つの段階から構成される。
- 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
- ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
となる
目次 |
アルゴリズム [編集]
ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の 配列 だけで表現できるという利点がある。ヒープソートを実装する際には、この利点を使い、元データの配列として確保された領域をヒープ構造や整列済みリストに転用していく。
最初にN個のデータを含む配列が与えられるものとする。添字は1 〜 Nとする。
まず各データをヒープ構造に登録していく。m個のデータを処理した状態では、添字1 〜 mがヒープ構造で、(m + 1) 〜 Nが未整列リストとなる。m + 1個目のデータを取り出し、ヒープ構造に登録する。このとき構成するヒープは、昇順にソートする場合はルートが最大値になるよう、降順にソートする場合はルートが最小値になるよう構成すると良い。
すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しに移る。ヒープのルートを取り出し、配列の後ろから詰めていく。mを Nから1まで減じながら、取り出したルート要素を配列の添字mに置く。すなわち、(N - m)個のデータを取り出した状態では添字1 〜 mがヒープ構造であり、m + 1 ～ Nが整列済みリストとなる。
すべてのデータをヒープ構造から取り出し終えると、配列全体が整列済みになる。
ヒープの操作の具体的な実装については、二分ヒープの記事を参照すること。
また、一般のヒープ操作では、根元側から木を成長させるのが普通だが、配列のようなデータ構造のヒープソートで、あらかじめ木の最終的な大きさがわかっている場合は、木の葉の側から順番にヒープを構築すると、より効率が良い（この記事で示す実装例では使っていない）。
実装例 [編集]
static void upheap(double arr[], int n); static void downheap(double arr[], int n); static inline void swap(double arr[], int a, int b) { double tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } void heapsort(double arr[], int n_elems) { int i = 0; /* * arr の先頭から順に、ヒープを成長させる * 0 1 2 | 3 4 5 * [ ] [ ] [ ]|[ ] [ ] [ ] * ヒープ | 未処理の入力 * ===> * i は、ヒープ中の要素数であると同時に、未処理データの先頭を * 指してもいる */ /* 配列が全部ヒープに入れ替わるまで繰り返す */ while (++i < n_elems) { /* * 配列の先頭要素を、ヒープの最後に移動するわけだが、どちらも * ちょうど同じ場所に最初からあるので、境界を移動させるだけでよい */ /* * arr[i] に、ヒープに新しく追加されたデータがあるものとして、 * 先頭から arr[i] までがヒープになるよう再構成する */ upheap(arr, i); } /* * arr の末端から順に、ヒープから取り出して並べる * 0 1 2 | 3 4 5 * [ ] [ ] [ ]|[ ] [ ] [ ] * ヒープ | ソート済みの配列 * <=== */ /* ヒープが全部配列に入れ替わるまで繰り返す */ while (--i > 0) { /* * ヒープの先頭要素を、配列に移動すると同時に、ヒープの最後の * 要素を、ヒープの先頭に移動する swap */ swap(arr, 0, i); /* * arr[0] に、ヒープの最後から移動されたデータがあるものとして、 * 先頭から arr[i - 1] までがヒープになるよう再構成する */ downheap(arr, i); } } /* * macros for heaptree * for 0 origin array */ #define LEFT_CHILD(i) (((i) + 1) * 2 - 1) #define RIGHT_CHILD(i) (((i) + 1) * 2) #define PARENT(i) (((i) + 1) / 2 - 1) /* * arr[n] に、ヒープに新しく追加されたデータがあるものとして、 * 先頭から arr[n] までがヒープになるよう再構成する */ static void upheap(double arr[], int n) { while (n > 0) { int m = PARENT(n); if (arr[m] < arr[n]) { swap(arr, m, n); } else { break; } n = m; } } /* * arr[0] に、ヒープの最後から移動されたデータがあるものとして、 * 先頭から arr[n - 1] までがヒープになるよう再構成する */ static void downheap(double arr[], int n) { int m = 0; int tmp = 0; for (;;) { int l_chld = LEFT_CHILD(m); int r_chld = RIGHT_CHILD(m); if (l_chld >= n) { break; } if (arr[l_chld] > arr[tmp]) { tmp = l_chld; } if ((r_chld < n) && (arr[r_chld] > arr[tmp])) { tmp = r_chld; } if (tmp == m) { break; } swap(arr, tmp, m); m = tmp; } }
補足 [編集]
ここで示した実装では原理と一般的な手法を示すため、細かいチューニングはしていない。ルートの要素を番兵にして比較を節約する、スワップではなくループの外で定義した一時変数に退避するようにして無用な「書いたものを読んで」を減らす、最初からヒープの最終的な大きさがわかっているので、木を葉のほうから構築する、といった改善が可能な点がある（参考文献『珠玉のプログラミング』の該当コラムの「問題」の節と巻末の解説を参照のこと）。
実装例２ [編集]
ヒープソートは一般に配列を使った完全２分木で実装される。そのためリストや木構造のデータに基本をおく関数型プログラミング言語で実装するには工夫が必要である。ここでは Haskell を使ったヒープソートの実装例を示す。
import Data.List (sort) import System.Random (getStdGen, randoms) data Hand = L | R -- ２分木の枝の型(L:左、R:右) type Path = [Hand] -- ノード番号最大のノードへのパスの型 type MaxNodeNum = Int -- ノード番号の型(根(root)の番号が1) data Tree a = Empty | Node !a !(Tree a) !(Tree a) -- ２分木の型 data Heap a = Heap !MaxNodeNum !(Tree a) -- ヒープの型(完全２分木) -- Heap 0 Empty はノードが一つもない空の完全２分木 -- ノード番号 nn へのパス {-# INLINE maxPath #-} maxPath :: MaxNodeNum -> Path maxPath nn = maxPath0 nn [] where maxPath0 :: Int -> Path -> Path maxPath0 1 xs = xs maxPath0 n xs | even n = maxPath0 (n `div` 2) (L:xs) -- ノード番号が偶数なら左 | odd n = maxPath0 (n `div` 2) (R:xs) -- ノード番号が奇数なら右 -- ヒープへの要素 xx の挿入 {-# INLINE insert #-} insert :: (Ord a) => Heap a -> a -> Heap a insert (Heap n t) xx = Heap (succ n) (insert0 path t xx) where path = maxPath (succ n) -- 最大ノード番号を1増やす -- 再帰の初段のみ特別な処理 insert0 :: (Ord a) => Path -> Tree a -> a -> Tree a insert0 (L:ps) (Node e l r) x = Node z ll r where (ll, z) = insert1 ps l x e insert0 (R:ps) (Node e l r) x = Node z l rr where (rr, z) = insert1 ps r x e insert0 _ _ x = Node x Empty Empty -- ノード番号最大の位置へ要素を挿入後、upheap を行う insert1 :: (Ord a) => Path -> Tree a -> a -> a -> (Tree a, a) insert1 (L:ps) (Node e l r) x y = (Node c ll r, p) where (ll, z) = insert1 ps l x e (p, c) = if y < z then (z, y) else (y, z) insert1 (R:ps) (Node e l r) x y = (Node c l rr, p) where (rr, z) = insert1 ps r x e (p, c) = if y < z then (z, y) else (y, z) insert1 _ _ x y = (Node c Empty Empty, p) where (p, c) = if y < x then (x, y) else (y, x) -- ヒープからの最大値の削除 {-# INLINE deleteMax #-} deleteMax :: (Ord a) => Heap a -> Heap a deleteMax = downHeap . leafToRoot where -- 準ヒープからのヒープの再構成 downHeap :: (Ord a) => Heap a -> Heap a downHeap h@(Heap 0 Empty) = h downHeap (Heap n tt) = Heap n (downHeap0 tt) where downHeap0 :: (Ord a) => Tree a -> Tree a downHeap0 t@(Node x l@(Node y l1 r1) r@(Node z l2 r2)) | y < z = if x < z then Node z l (downHeap0 (Node x l2 r2)) else t | otherwise = if x < y then Node y (downHeap0 (Node x l1 r1)) r else t downHeap0 t@(Node x (Node y Empty Empty) Empty) | x < y = Node y (Node x Empty Empty) Empty | otherwise = t downHeap0 t = t -- ノード番号最大の葉をヒープから切り離し、その要素を根(root)に代入 leafToRoot :: Heap a -> Heap a leafToRoot (Heap 1 _) = Heap 0 Empty leafToRoot (Heap n t) = Heap (pred n) (Node x l r) where path = maxPath n (Node _ l r, x) = leafcut path t leafcut :: Path -> Tree a -> (Tree a, a) leafcut (L:ps) (Node e l r) = (Node e ll r, x) where (ll, x) = leafcut ps l leafcut (R:ps) (Node e l r) = (Node e l rr, x) where (rr, x) = leafcut ps r leafcut _ (Node e _ _) = (Empty, e) -- リストからヒープを構成する {-# INLINE makeHeap #-} makeHeap :: (Ord a) => [a] -> Heap a makeHeap = foldl upHeap (Heap 0 Empty) where -- upheap は挿入と等価 upHeap :: (Ord a) => Heap a -> a -> Heap a upHeap = insert -- ヒープの最大値を返す {-# INLINE findMax #-} findMax :: Heap a -> a findMax (Heap _ (Node x _ _)) = x -- ヒープソート(リスト xxs をソートして返す) {-# INLINE heapsort #-} heapsort :: (Ord a) => [a] -> [a] heapsort xxs = heapsort0 (makeHeap xxs) [] where heapsort0 :: (Ord a) => Heap a -> [a] -> [a] heapsort0 (Heap 0 Empty) xs = xs heapsort0 h xs = heapsort0 (deleteMax h) (findMax h:xs) -- 正しくソート出来たかをチェックする check :: Bool -> String check x = if x then "OK" else "NG" -- メインルーチン(ここでは、ヒープソートが正しいかチェックしている) main = do g <- getStdGen let rs3 = take 12345 $ randoms g :: [Int] -- 乱数列の生成 rs2 = take 1234 rs3 rs1 = take 123 rs3 putStr $ (++ " ") $ show $ length rs1 print $ check $ heapsort rs1 == sort rs1 putStr $ (++ " ") $ show $ length rs2 print $ check $ heapsort rs2 == sort rs2 putStr $ (++ " ") $ show $ length rs3 print $ check $ heapsort rs3 == sort rs3
C言語での実装にアルゴリズムをあわせてあるので Haskell としては多少不自然だが、リストと木構造と再帰でヒープソートを実現できている。insert, deleteMax, findMax はそのまま優先度つきキューとしても使える。しかし、実用面から見ると、より Haskell に適した leftist heap や skew heap を用いた方法の方が簡単で効率的である。
特徴 [編集]
- データの出現順序による計算量の変化が小さい（クイックソートでは最悪の場合O
となってしまう）[1]。ただし、平均的にはクイックソートより遅い[1]。 - ソート対象のデータ自体以外に必要となる作業領域の大きさは固定で、データ量に依存しない。
となってしまう）ただし以下のように、現代のコンピュータで用いられる高速化技法に適さない特徴があることにも注意する必要がある。
脚注 [編集]
関連項目 [編集]
参考文献 [編集]
- ジョン・ベントリー 『珠玉のプログラミング』（コラム14）小林健一郎訳、ピアソン・エデュケーション、2000年、ISBN 4-89471-236-9。
外部リンク [編集]
|
||||||||||||||||||||||||||||||||
