Go实现基于二叉堆的优先队列

这次遇到了一些坑,Go中的语法对于用惯了Java的来说,还是有不少区别的。

代码实现

package priorityqueue

type Node interface {
    /*
    return the value < i
     */
    Comparable(i Node) bool
}

type  priorityqueue struct {
    pq []Node
}

func NewPriorityQueue() *priorityqueue {
    return &priorityqueue{pq:make([]Node, 1, 10)}
}

func (q *priorityqueue) IsEmpty() bool {
    return q.len() == 0
}

func (q *priorityqueue)Size() int {
    return q.len()
}

func (q *priorityqueue)Insert(v Node) {
    q.pq = append(q.pq, v)
    q.swim(q.len())
}

func (q *priorityqueue)DelMax() Node {
    max := q.pq[1]
    q.exch(1, q.len())
    q.pq = q.pq[:q.len()]
    q.sink(1)
    return max
}

func (q *priorityqueue)less(i, j int) bool {
    return q.pq[i].Comparable(q.pq[j])
}

func (q *priorityqueue)exch(i, j int) {
    q.pq[i], q.pq[j] = q.pq[j], q.pq[i]
}

func (q *priorityqueue)swim(k int) {
    for (k > 1 && q.less(k / 2, k)) {
        q.exch(k / 2, k)
        k = k / 2
    }
}

func (q *priorityqueue)sink(k int) {
    for (k * 2 <= q.len()) {
        j := k * 2
        if j < q.len() && q.less(j, j + 1) {
            j++
        }
        if !q.less(k, j) {
            break
        }
        q.exch(k, j)
        k = j
    }
}

func (q *priorityqueue)len() int {
    return len(q.pq) - 1
}
文章目录
  1. 1. 代码实现