優先順位つき待ち行列

優先順位付き待ち行列

• お尻から入れて頭から出す
• お尻から要素が入ってくるけれど，頭から出てくるときには特定の優先順位に従って要素が出てくる（入れた順番によって出てくる順番が決まるわけではない）
• 優先順位つき待ち行列は，挿入・削除・最(大|小)値の取り出し・要素の値の変更が$O(\log n)$でできるので，とってもとっても便利屋さん
  • Goでは標準ライブラリで実装が提供されている => container/heap
  • 標準ライブラリはInterfaceを定義して，いろんなデータを抱えている配列を柔軟にヒープせしめることができるように設計されている（頭いいなぁ）
• ヒープは**「優先度つき待ち行列を合併して大きな優先度つき待ち行列を一つ作る」**ことは苦手
• 優先度つき待ち行列を実現する方法はヒープだけではなくて他のデータ構造を用いてもできる．二分木じゃなくて$d$分木とか．あと，値全体を一つの部分順序つき木に入れるんじゃなくて，複数の木に分散させて，木の集合つまり森を管理するようなデータ構造も提案されているらしい
• 以下では，優先順位付のルールとして「今入っている要素の大きい順で出すこと」にする

「配列上に表現された部分順序つき木（＝ヒープ）」で優先順位つき待ち行列

初期化

• 与えられた初期値から部分順序つき木を構成する

その時点での最大値を出す

• 部分順序つき木の根っこを出して，再構成

要素の削除

• 特定の要素を添字で指定して削除して，再構成

要素をお尻から入れる

• 部分順序つき木の末端に追加して，再構成

値を更新する

• 更新してから，再構成

package main

import "log"

type PriorityQueue []int

func (pq *PriorityQueue) Init() {
	n := len(*pq)
	for i := n/2 - 1; i >= 0; i-- {
		pq.downheap(i, n)
	}
}

func (pq *PriorityQueue) PopFront() int {
	n := len(*pq) - 1
	ret := (*pq)[0]
	(*pq)[0], (*pq)[n] = (*pq)[n], (*pq)[0]
	pq.downheap(0, n)
	*pq = (*pq)[:len(*pq)-1]
	return ret
}

func (pq *PriorityQueue) PushBack(value int) {
	*pq = append(*pq, []int{value}...)
	pq.upheap(len(*pq))
}

func (pq *PriorityQueue) Delete(idx int) {
	n := len(*pq) - 1
	oldValue := (*pq)[idx]
	if n != idx {
		(*pq)[idx], (*pq)[n] = (*pq)[n], (*pq)[idx]
		if (*pq)[idx] < oldValue {
			pq.downheap(idx, n)
		} else {
			pq.upheap(idx)
		}
	}
}

func (pq *PriorityQueue) Update(value int) {
	n := len(*pq) + 1
	*pq = append(*pq, []int{value}...)
	pq.upheap(n)
}

func (pq *PriorityQueue) downheap(parent, length int) {
	for {
		children := 2*parent + 1
		if children >= length || children < 0 {
			break
		}
		child := children // left child
		if rightChild := child + 1; rightChild < length && (*pq)[rightChild] > (*pq)[child] {
			child = rightChild
		}
		if (*pq)[child] < (*pq)[parent] {
			break
		}
		(*pq)[child], (*pq)[parent] = (*pq)[parent], (*pq)[child]
		parent = child // down
	}
}

func (pq *PriorityQueue) upheap(children int) {
	for {
		parent := (children-1)/2
		if children == parent || (*pq)[children] < (*pq)[parent] {
			break
		}
		(*pq)[children], (*pq)[parent] =  (*pq)[parent], (*pq)[children]
		children = parent // up
	}
}

func main() {
	pq := PriorityQueue{6, 7, 1, 0, 5, 9, 4, 8, 2, 3}
	pq.Init()
	log.Println(pq)
	for i := 0; i < 10; i++ {
		log.Println(pq.PopFront())
	}
}

• 標準ライブラリは便利に作られててかしこかしこやなぁと．改めて．