【算法笔记】PriorityQueue的简单实践

今天用go语言简单的写了一下PriorityQueue的方法。
为了以后方便查看，当做笔记整理了一下~~

1.优先队列(PriorityQueue)

维基百科里是这么解释的。

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；
优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

下面用go语言简单的实现了PriorityQueue。

struct

type PriorityQueue struct {
    Head *Node
}

type Node struct {
    Value    string
    Priority int
    Next     *Node
}

Push

func (p *PriorityQueue) Push(value string, priority int) {
    if p.Head == nil {
        p.Head = &Node{Value: value, Priority: priority}
        return
    }
    newNode := &Node{Value: value, Priority: priority}
    currentNode := p.Head
    for currentNode.Next != nil && currentNode.Next.Priority > priority {
        currentNode = currentNode.Next
    }
    newNode.Next = currentNode.Next
    currentNode.Next = newNode
}

Pop

func (p *PriorityQueue) Pop() *Node {
    if p.Head == nil {
        return nil
    }
    result := p.Head
    p.Head = p.Head.Next
    return result
}

Peek,IsEmpty,Print

func (p *PriorityQueue) Peek() *Node {
    return p.Head
}

func (p *PriorityQueue) IsEmpty() bool {
    return p.Head == nil
}

func (n *Node) Print() {
    if n == nil {
        return
    }
    fmt.Print(n.Value, " ")
    n.Next.Print()
}

执行结果

func main() {
    priorityQueue := PriorityQueue{}
    priorityQueue.Push("a", 100)
    priorityQueue.Push("b", 83)
    priorityQueue.Push("c", 64)
    priorityQueue.Push("e", 37)
    priorityQueue.Push("f", 23)

    fmt.Println("-------- Print  --------")
    priorityQueue.Head.Print()
    fmt.Println("")

    fmt.Println("-------- Pop  --------")
    fmt.Printf("%+v", priorityQueue.Pop())
    fmt.Println("")
    priorityQueue.Head.Print()
    fmt.Println("")

    fmt.Println("-------- Push z --------")
    priorityQueue.Push("z", 53)
    priorityQueue.Head.Print()
    fmt.Println("")

    fmt.Println("-------- Peek()  --------")
    fmt.Printf("%+v", priorityQueue.Peek()) 
}

执行结果为：

$ go run main.go
-------- Print  --------
a b c e f 
-------- Pop  --------
&{Value:a Priority:100 Next:0xc0000a43c0}
b c e f
-------- Push z --------
b c z e f
-------- Peek()  --------
&{Value:b Priority:83 Next:0xc0000a43e0}

欢迎大家的意见和交流

email: li_mingxie@163.com