Golang最大堆

在Go語言中，最大堆（Max-Heap）是一種數據結構，它是二叉堆的一種特殊形式，其中每個節點的值都不小於其子節點的值。最大堆通常用於實現優先佇列，其中堆頂的元素總是最大或最小的。

在Go語言中，你可以使用數組來實現最大堆。以下是一個簡單的最大堆實現示例：

package main

import "fmt"

type MaxHeap struct {
    data []int
}

func NewMaxHeap(arr []int) *MaxHeap {
    n := len(arr)
    if n == 0 {
        return nil
    }
    return &MaxHeap{data: arr}
}

func (h *MaxHeap) BuildHeap() {
    n := len(h.data)
    for i := n/2 - 1; i >= 0; i-- {
        h.heapify(i, n)
    }
}

func (h *MaxHeap) heapify(i, n int) {
    largest := i
    l := 2*i + 1
    r := 2*i + 2
    if l < n && h.data[l] > h.data[largest] {
        largest = l
    }
    if r < n && h.data[r] > h.data[largest] {
        largest = r
    }
    if largest != i {
        h.data[i], h.data[largest] = h.data[largest], h.data[i]
        h.heapify(largest, n)
    }
}

func (h *MaxHeap) ExtractMax() int {
    if h.IsEmpty() {
        return -1
    }
    n := len(h.data) - 1
    h.data[0], h.data[n] = h.data[n], h.data[0]
    h.data[n] = 0
    h.heapify(0, n)
    return h.data[0]
}

func (h *MaxHeap) IsEmpty() bool {
    return len(h.data) == 0
}

func (h *MaxHeap) Size() int {
    return len(h.data)
}

func (h *MaxHeap) Peek() int {
    if h.IsEmpty() {
        return -1
    }
    return h.data[0]
}

func main() {
    arr := []int{3, 4, 1, 16, 9, 10}
    heap := NewMaxHeap(arr)
    heap.BuildHeap()
    fmt.Println(heap.Peek())
    fmt.Println(heap.ExtractMax())
    fmt.Println(heap.Peek())
}

在這個例子中，MaxHeap 結構體包含一個數組 data，其中存儲了堆的元素。BuildHeap 方法用於將給定的數組轉換為最大堆。ExtractMax 方法用於提取堆頂元素，Peek 方法用於查看堆頂元素而不移除它。IsEmpty 和 Size 方法用於檢查堆是否為空和獲取堆的大小。

請注意，這個例子只實現了最大堆的基本操作，沒有實現優先佇列的插入操作。如果你需要實現插入操作，你可以使用Insert方法將新元素添加到數組的最後一個位置，然後調整堆結構，使其保持最大堆的性質。