缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

堆

  1. 堆是一种图的树形结构，
  2. 被用于实现“优先队列”（priority queues）。
  3. 优先队列是一种数据结构，
  4. 可以自由添加数据，
  5. 但取出数据时要从最小值开始按顺序取出。
  7. 在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。
  9. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

补充知识

  • 堆又名二叉堆, 是一种无序完全二叉树
  • 所谓完全, 是指节点从上至下, 从左至右填充, 中间不会留有空隙
  • 完全二叉树可以使用数组存放, 因为其父节点与左右子节点的索引存在线性关系, 以0下标为例
    • parent.index = (child.index - 1) / 2, 如: 0 = (1 - 1) / 2, 0 = (2 - 1) / 2
    • left.index = parent.index 2 + 1, 如: 1 = 0 2 + 1
    • right.index = left.index + 1
  • 添加数据时
    • 先把数据添加到最末尾, 也就是堆的右下角
    • 然后跟父节点比较大小, 如果小于父节点, 则交换之, 又名上浮
    • 重复上浮的过程, 直到满足堆的规则: 父节点总是小于子节点
  • 弹出数据时
    • 总是弹出堆顶, 也就是最小值
    • 然后把堆的末尾值, 放到堆顶. 移动末尾值, 不会留下中间间隙, 保持完全二叉树的状态
    • 如果堆顶值大于某个子节点的值, 则与最小值节点交换, 又名下沉
    • 重复下沉的过程, 直到满足堆的规则: 父节点总是小于子节点

目标

  • 基于数组实现二叉堆, 并验证堆排序的功能

设计

  • IComparator: 值大小比较器接口. 通过翻转比较函数, 也可以创建最大堆(顶点值最大).
  • IHeap: 定义堆的接口
  • IIterator: 堆迭代器接口
  • tComparator: 值大小比较器, 实现IComparator接口, 具体比较函数由外部传入
  • tArrayHeap: 二叉堆, 实现IHeap接口
  • tHeapIterator: 堆迭代器, 实现IIterator接口

单元测试

heap_test.go, 验证二叉堆的基本功能, 并通过随机Push和有序Pop, 观察堆排序的效果

  1. package data_structure
  3. import (
  4.     "fmt"
  5.     "learning/gooop/data_structure/heap"
  6.     "math/rand"
  7.     "strings"
  8.     "testing"
  9.     "time"
  10. )
  12. func Test_Heap(t *testing.T) {
  13.     fnAssertTrue := func(b bool, msg string) {
  14.         if !b {
  15.             panic(msg)
  16.         }
  17.     }
  19.     fnLess := func(a interface{}, b interface{}) bool {
  20.         i1 := a.(int)
  21.         i2 := b.(int)
  22.         return i1 < i2
  23.     }
  24.     comparator := heap.NewComparator(fnLess)
  26.     // test empty heap
  27.     hp := heap.NewArrayHeap(comparator)
  28.     fnAssertTrue(hp.Size() == 0, "expecting size == 0")
  29.     fnAssertTrue(hp.IsEmpty(), "expecting empty")
  30.     fnAssertTrue(hp.Iterator().More() == false, "expecting !more")
  32.     e,_ := hp.Pop()
  33.     fnAssertTrue(e != nil, "expecting e != nil")
  35.     // push random samples
  36.     rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  37.     samples := 13
  38.     for i := 0;i < samples;i++ {
  39.         hp.Push(rnd.Intn(100))
  40.     }
  41.     t.Log(hp)
  43.     // test iterator
  44.     iter := hp.Iterator()
  45.     itemStrings := make([]string, 0)
  46.     for i := 0;i < samples;i++ {
  47.         e, v := iter.Next()
  48.         fnAssertTrue(e == nil, "expecting e == nil")
  49.         itemStrings = append(itemStrings, fmt.Sprintf("%v", v))
  50.     }
  51.     fnAssertTrue(iter.More() == false, "expecting !more")
  52.     e,_ = iter.Next()
  53.     fnAssertTrue(e != nil, "expecting e != nil")
  54.     t.Log(strings.Join(itemStrings, ","))
  56.     // test heap sort
  57.     prev := -1
  58.     size := hp.Size()
  59.     for i := 0;i < size;i++ {
  60.         e,v := hp.Pop()
  61.         fnAssertTrue(e == nil, "expecting e == nil")
  63.         n := v.(int)
  64.         t.Logf("%d = %d", i, n)
  65.         if prev >= 0 {
  66.             fnAssertTrue(prev <= n, "expecting prev <= n")
  67.             prev = n
  68.         }
  69.         prev = n
  70.     }
  71.     fnAssertTrue(hp.IsEmpty(), "expecting empty")
  73.     // test 0-9
  74.     for i := 0;i < 10;i++ {
  75.         hp.Push(i)
  76.     }
  77.     itemStrings = make([]string, 0)
  78.     for ;hp.IsNotEmpty(); {
  79.         e,v := hp.Pop()
  80.         fnAssertTrue(e == nil, "expecting e == nil")
  81.         itemStrings = append(itemStrings, fmt.Sprintf("%v", v))
  82.     }
  83.     s := strings.Join(itemStrings, ",")
  84.     t.Log(s)
  85.     fnAssertTrue(s == "0,1,2,3,4,5,6,7,8,9", "expecting 0-9")
  86. }

测试输出

  1. $ go test -v heap_test.go 
  2. === RUN   Test_Heap
  3.     heap_test.go:41: 
  4.            0
  5.           12,  36
  6.           36,  17,  37,  53
  7.           69,  37,  79,  22,  69,  37
  8.     heap_test.go:54: 0,12,36,36,17,37,53,69,37,79,22,69,37
  9.     heap_test.go:64: 0 = 0
  10.     heap_test.go:64: 1 = 12
  11.     heap_test.go:64: 2 = 17
  12.     heap_test.go:64: 3 = 22
  13.     heap_test.go:64: 4 = 36
  14.     heap_test.go:64: 5 = 36
  15.     heap_test.go:64: 6 = 37
  16.     heap_test.go:64: 7 = 37
  17.     heap_test.go:64: 8 = 37
  18.     heap_test.go:64: 9 = 53
  19.     heap_test.go:64: 10 = 69
  20.     heap_test.go:64: 11 = 69
  21.     heap_test.go:64: 12 = 79
  22.     heap_test.go:84: 0,1,2,3,4,5,6,7,8,9
  23. --- PASS: Test_Heap (0.00s)
  24. PASS
  25. ok      command-line-arguments  0.002s

IComparator.go

值大小比较器接口. 通过翻转比较函数, 也可以创建最大堆(顶点值最大).

  1. package heap
  3. type IComparator interface {
  4.     Less(a interface{}, b interface{}) bool
  5. }

IHeap.go

定义堆的接口

  1. package heap
  3. type IHeap interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Push(value interface{})
  9.     Pop() (error, interface{})
  11.     Iterator() IIterator
  12.     String() string
  13. }

IIterator.go

堆迭代器接口

  1. package heap
  3. type IIterator interface {
  4.     More() bool
  5.     Next() (error,interface{})
  6. }

tComparator.go

值大小比较器, 实现IComparator接口, 具体比较函数由外部传入

  1. package heap
  3. import "errors"
  5. type FnLess func(a interface{}, b interface{}) bool
  7. type tComparator struct {
  8.     fnLess FnLess
  9. }
  11. func NewComparator(fn FnLess) IComparator {
  12.     if fn == nil {
  13.         panic(gNullArgumentError)
  14.     }
  16.     return &tComparator{
  17.         fnLess: fn,
  18.     }
  19. }
  22. func (me *tComparator) Less(a interface{}, b interface{}) bool {
  23.     if a == nil || b == nil {
  24.         panic(gNullArgumentError)
  25.     }
  26.     return me.fnLess(a, b)
  27. }
  30. var gNullArgumentError = errors.New("null argument error")

tArrayHeap.go

二叉堆, 实现IHeap接口

  1. package heap
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "strings"
  7. )
  9. type tArrayHeap struct {
  10.     comparator IComparator
  11.     items []interface{}
  12.     size int
  13.     version int64
  14. }
  16. func NewArrayHeap(comparator IComparator) IHeap {
  17.     return &tArrayHeap{
  18.         comparator: comparator,
  19.         items: make([]interface{}, 0),
  20.         size: 0,
  21.         version: 0,
  22.     }
  23. }
  25. func (me *tArrayHeap) Size() int {
  26.     return me.size
  27. }
  29. func (me *tArrayHeap) IsEmpty() bool {
  30.     return me.size <= 0
  31. }
  33. func (me *tArrayHeap) IsNotEmpty() bool {
  34.     return !me.IsEmpty()
  35. }
  37. func (me *tArrayHeap) Push(value interface{}) {
  38.     me.version++
  40.     me.ensureSize(me.size + 1)
  41.     me.items[me.size] = value
  42.     me.size++
  44.     me.shiftUp(me.size - 1)
  45.     me.version++
  46. }
  49. func (me *tArrayHeap) ensureSize(size int) {
  50.     for ;len(me.items) < size; {
  51.         me.items = append(me.items, nil)
  52.     }
  53. }
  55. func (me *tArrayHeap) parentOf(i int) int {
  56.     return (i - 1) / 2
  57. }
  59. func (me *tArrayHeap) leftChildOf(i int) int {
  60.     return i*2 + 1
  61. }
  63. func (me *tArrayHeap) rightChildOf(i int) int {
  64.     return me.leftChildOf(i) + 1
  65. }
  67. func (me *tArrayHeap) last() (i int, v interface{}) {
  68.     if me.IsEmpty() {
  69.         return -1, nil
  70.     }
  72.     i = me.size - 1
  73.     v = me.items[i]
  74.     return i,v
  75. }
  77. func (me *tArrayHeap) shiftUp(i int) {
  78.     if i <= 0 {
  79.         return
  80.     }
  81.     v := me.items[i]
  83.     pi := me.parentOf(i)
  84.     pv := me.items[pi]
  86.     if me.comparator.Less(v, pv) {
  87.         me.items[pi], me.items[i] = v, pv
  88.         me.shiftUp(pi)
  89.     }
  90. }
  92. func (me *tArrayHeap) Pop() (error, interface{}) {
  93.     if me.IsEmpty() {
  94.         return gNoMoreElementsError, nil
  95.     }
  97.     me.version++
  99.     top := me.items[0]
  100.     li, lv := me.last()
  101.     me.items[0] = nil
  102.     me.size--
  104.     if me.IsEmpty() {
  105.         return nil, top
  106.     }
  108.     me.items[0] = lv
  109.     me.items[li] = nil
  111.     me.shiftDown(0)
  112.     me.version++
  114.     return nil, top
  115. }
  117. func (me *tArrayHeap) shiftDown(i int) {
  118.     pv := me.items[i]
  119.     ok, ci, cv := me.minChildOf(i)
  120.     if ok && me.comparator.Less(cv, pv) {
  121.         me.items[i], me.items[ci] = cv, pv
  122.         me.shiftDown(ci)
  123.     }
  124. }
  126. func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {
  127.     li := me.leftChildOf(p)
  128.     if li >= me.size {
  129.         return false, 0, nil
  130.     }
  131.     lv := me.items[li]
  133.     ri := me.rightChildOf(p)
  134.     if ri >= me.size {
  135.         return true, li, lv
  136.     }
  137.     rv := me.items[ri]
  139.     if me.comparator.Less(lv, rv) {
  140.         return true, li, lv
  141.     } else {
  142.         return true, ri, rv
  143.     }
  144. }
  146. func (me *tArrayHeap) Iterator() IIterator {
  147.     return newHeapIterator(me)
  148. }
  150. func (me *tArrayHeap) String() string {
  151.     level := 0
  152.     lines := make([]string, 0)
  153.     lines = append(lines, "")
  155.     for {
  156.         n := 1<<level
  157.         min := n - 1
  158.         max := n + min - 1
  159.         if min >= me.size {
  160.             break
  161.         }
  163.         line := make([]string, 0)
  164.         for i := min;i <= max;i++ {
  165.             if i >= me.size {
  166.                 break
  167.             }
  168.             line = append(line, fmt.Sprintf("%4d", me.items[i]))
  169.         }
  170.         lines = append(lines, strings.Join(line, ","))
  172.         level++
  173.     }
  175.     return strings.Join(lines, "\n")
  176. }
  178. var gNoMoreElementsError = errors.New("no more elements")

tHeapIterator.go

堆迭代器, 实现IIterator接口

  1. package heap
  3. import "errors"
  5. type tHeapIterator struct {
  6.     heap *tArrayHeap
  7.     pos int
  8.     version int64
  9. }
  11. func newHeapIterator(heap *tArrayHeap) IIterator {
  12.     return &tHeapIterator{
  13.         heap: heap,
  14.         pos: 0,
  15.         version: heap.version,
  16.     }
  17. }
  19. func (me *tHeapIterator) More() bool {
  20.     if me.version != me.heap.version {
  21.         return false
  22.     }
  23.     return me.pos < me.heap.size
  24. }
  26. func (me *tHeapIterator) Next() (error, interface{}) {
  27.     if me.version != me.heap.version {
  28.         return gConcurrentModificationError, nil
  29.     }
  31.     if me.pos >= me.heap.size {
  32.         return gNoMoreElementsError, nil
  33.     }
  35.     v := me.heap.items[me.pos]
  36.     me.pos++
  37.     return nil, v
  38. }
  40. var gConcurrentModificationError = errors.New("concurrent modification error")

(end)