# 算法导论第六章-最小优先队列

``````package main

// MinHeap 最小堆的结构
type MinHeap struct {
heapSize int
heap     []int
}

// LEFT 返回子树左边的元素
func (A *MinHeap) LEFT(i int) int {
return i << 1
}

// RIGHT 返回子树右边的元素
func (A *MinHeap) RIGHT(i int) int {
return (i<<1 + 1)
}

// PARENT 返回父结点
func (A *MinHeap) PARENT(i int) int {
return i >> 1
}

// MinHeapify 最小化堆
func (A *MinHeap) MinHeapify(i int) {
smallest := i
l := A.LEFT(i + 1)
r := A.RIGHT(i + 1)
if l <= A.heapSize && A.heap[l-1] < A.heap[i] {
smallest = l - 1
}
if r <= A.heapSize && A.heap[r-1] < A.heap[smallest] {
smallest = r - 1
}
if smallest != i {
A.heap[smallest], A.heap[i] = A.heap[i], A.heap[smallest]
A.MinHeapify(smallest)
}
}

// BuildMinHeap 构建最小堆
func (A *MinHeap) BuildMinHeap() {
for i := A.heapSize / 2; i >= 0; i-- {
A.MinHeapify(i)
}
}

// GetHeapSize 获得堆大小
func (A *MinHeap) GetHeapSize() int {
return A.heapSize
}

// AlterHeapSize 更改堆大小
func (A *MinHeap) AlterHeapSize(i int) {
A.heapSize = i
}

// GetElement 获得堆中的元素
func (A *MinHeap) GetElement(i int) int {
return A.heap[i]
}

// SetElement 更新堆中的元素
func (A *MinHeap) SetElement(i int, key int) {
A.heap[i] = key
}

// Swap 交换堆中的元素
func (A *MinHeap) Swap(i int, j int) {
A.heap[i], A.heap[j] = A.heap[j], A.heap[i]
}

// Append 向堆中追加元素
func (A *MinHeap) Append(i int) {
A.heap = append(A.heap, i)
}

// NewMinHeap 最小里堆的构造函数
func NewMinHeap(heapSize int, a []int) *MinHeap {
minHeap := MinHeap{heapSize: heapSize, heap: a}
minHeap.BuildMinHeap()
return &minHeap
}
``````

``````package main

import (
"errors"
"fmt"
)

// MinHeapInterface 最小堆的接口
type MinHeapInterface interface {
LEFT(i int) int
RIGHT(i int) int
PARENT(i int) int
MinHeapify(i int)
BuildMinHeap()
GetHeapSize() int
AlterHeapSize(int)
GetElement(i int) int
Swap(i int, j int)
SetElement(i int, key int)
Append(i int)
}

// MinPriorityQueue 最小队列的接口(只要实现了最小队列的那些方法就能实现最小队列)
type MinPriorityQueue interface {
MinHeapInterface
}

// Insert 把元素key插入到队列S中
func Insert(S MinPriorityQueue, key int) {
const MaxInt = int(^uint(0) >> 1)
S.AlterHeapSize(S.GetHeapSize() + 1)
S.Append(MaxInt)
DecreaseKey(S, S.GetHeapSize()-1, key)
}

// Minimum 返回S中具有最小关键字的元素
func Minimum(S MinPriorityQueue) int {
return S.GetElement(0)
}

// ExtractMin 去掉并返回S中具有最小关键字的元素
func ExtractMin(S MinHeapInterface) (int, error) {
heapSize := S.GetHeapSize()
if heapSize < 1 {
return 0, errors.New("HEAP UNDERFLOW")
}
min := S.GetElement(0)
S.Swap(0, heapSize-1)
S.AlterHeapSize((heapSize - 1))
S.MinHeapify(0)
return min, nil
}

// DecreaseKey 将元素i的关键字减少到key,这里假设key的值不小于i的原关键字值
func DecreaseKey(S MinHeapInterface, i int, key int) error {
if key >= S.GetElement(i) {
return errors.New("new key is bigger than current key")
}
S.SetElement(i, key)
for i > 0 && S.GetElement(S.PARENT(i)) > S.GetElement(i) {
S.Swap(i, S.PARENT(i))
i = S.PARENT(i)
}
return nil
}

func main() {
s := []int{15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1}
a := NewMinHeap(len(s), s)
for a.heapSize > 0 {
i, _ := ExtractMin(a)
fmt.Println(i)
}
}
``````