sodefrin.work

ヒープソートとプライオリティキュー

アルゴリズムの勉強足りていないなと思いまして、アルゴリズムイントロダクションを読んでいます。アウトプットしておくと覚えがいいとのことなので、まとめていきます。

今回はヒープソートとプライオリティキューについて。

私は Go が好きなので Go の公式 package のsortcontainer/heapの実装についても触れます。

ヒープとは

完全 2 分木の中で、親要素と子要素の間に大小関係が存在するものをヒープといいます。

完全 2 分木は図 1 のように各ノードがちょうど 2 つの子ノードを持つような木構造です。

左上から順に数えることで図 2 のような配列として表現することもできます。

図1

heap

図 2

heap-array

max ヒープと min ヒープ

ヒープでは親要素と子要素の間に大小関係が存在します。

すべての親ノードが子ノードよりも必ず大きい場合 max ヒープ、すべての親ノードが子ノードよりも必ず小さい場合 min ヒープと呼びます。

例えば、図 3 は図 1 を max ヒープに並び替えたもの、図 4 は図 1 を min ヒープに並び替えたものです。

図 3

max-heap

図 4

min-heap

ヒープソートの仕組み

ヒープソートは以下のような手順で実行されます。

  • (1) 与えられた配列を max ヒープに並び替える (BUILD_MAX_HEAP)
  • (2) 先頭要素を取り出してヒープの長さを 1 短くし、末尾の要素を先頭に移動る
  • (3) 長さが 1 短くなったヒープをもう一度 max ヒープになるように並び変える (MAX_HEAPIFY)
  • (4) (2) に戻る

max ヒープの最も大きな要素を取り出す、もう一度 max ヒープを作り直すという手順を繰り返すことで、ソートを実現します。

ここでは、MAX_HEAPIFY と BUILD_MAX_HEAP について軽くまとめます。

MAX_HEAPIFY

MAX_HEAPIFY は、max ヒープの中に子ノードよりも小さな値を持つ親ノードがいた場合に、子ノードと位置を入れ替えていくことで、max ヒープを再構築する方法です。

具体的には、図 5 のように、先頭ノードが子ノードよりも小さいために、max ヒープになっていないようなヒープが与えられた際に、図 5-7 のような手順で値を入れ替えることで、max ヒープを再構築していきます。

図が多くなるので省略します。

図 5

max-heapify2

図 6

max-heapify2

図 7

max-heapify3

大きい方の子ノードと親ノードを交換していくことで、図 7 は max ヒープになっています。

BUILD_MAX_HEAP

MAX_HEAPIFY は、ヒープの先頭ノードのみが、max ヒープに従っていないような状態で使えるアルゴリズムですが、BUILD_MAX_HEAP は完全にランダムなヒープを max ヒープに構成します。

これは MAX_HEAPIFY を葉ノードから親ノードへ向けて順に実行していくことで実現されます。

Go におけるヒープソート

Go のsort packageでは、ソートアルゴリズムとしてクイックソートとヒープソートと挿入ソートが内部的に利用されています。

// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

...

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

(sort.go より)

要素数が少ない場合には単純な挿入ソートを、要素数が多い場合は平均的な性能に優れるクイックソートをまず試し、一定の試行回数でソートが完了しなかった場合にヒープソートに切り替わります。

これは、クイックソートの最悪計算量が N^2 であるのに対して、ヒープソートの最悪計算量が NlogN であることが理由であると思われます。

ヒープソート本体の実装は以下の通りです。

// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

...

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSort(data Interface, a, b int) {
	first := a
	lo := 0
	hi := b - a

	// Build heap with greatest element at top.
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}

	// Pop elements, largest first, into end of data.
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown(data, lo, i, first)
	}
}

(sort.go より)

上記のコードを読むと、heapSort 関数の前半部分が BUILD_MAX_HEAP 手続きに、shitDown 関数が MAX_HEAPIFY 手続きに対応していることがわかります。

プライオリティキューの仕組み

プライオリティキューもヒープを利用して実現されます。プリラオリティキューは、キューなので値の追加(PUSH)と取得(POP)の2つの操作を定義する必要があります。

PUSH

値の追加された際には、以下の更新処理を行うことで max ヒープを維持します。

  • (1) ヒープの長さを 1 大きくし、末尾に要素を追加します
  • (2) 新しく追加された要素が親要素よりも大きとき親要素と交換します
  • (3) (2)を、交換の必要がなくなるまで繰り返します

POP

値の取得の際には、以下の更新処理を行うことで max ヒープを維持します。

  • (1) 先頭要素を取り出してヒープの長さを 1 短くし、末尾の要素を先頭に移動する
  • (2) 長さが 1 短くなったヒープをもう一度 max ヒープになるように並び替える (MAX_HEAPIFY)

Go のcontainer/heap package

Go のcontainer/heap packageでは、プライオリティキューのための heap が実装されています。

こちらでは、Push 関数と Pop 関数が上記の PUSH、POP 手続きに対応した実装になっています。

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

...

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) interface{} {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

...

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

(heap.goより)

読書 プログラミング

このブログを書いている人

sodefrin
このブログでは、主に関心のある技術領域のアウロプットを行います。

最新の記事

ヒープソートとプライオリティキュー ずっと使えるFXチャート分析の基本(シンプルなテクニカル分析による売買ポイントの見つけ方) メルカリ稀代のスタートアップ、野心と焦りと挑戦の5年間 億万長者をめざすバフェットの銘柄選択術 About

カテゴリー一覧

プログラミング (1) 仕事 (1) 読書 (4)