Golang 程序将元素插入二叉堆
在二叉堆中插入元素意味着向堆中添加一个额外元素，同时保持堆属性。在这篇 Go 语言文章中，我们将编写一个程序将元素插入二叉堆。它是一种基于二叉树的数据结构，遵循堆属性。堆有两种类型:最小堆和最大堆。
在最小堆中，父节点的值小于其子节点的值，而在最大堆中，父节点的值大于其子节点的值。它们用于实现优先级队列、排序算法和图形算法。
语法
func append(slice, element_1, element_2…, element_N) []T
append 函数用于将值添加到数组切片。它需要多个参数。第一个参数是我们希望添加值的数组，后面跟着要添加的值。然后，该函数返回包含所有值的数组的最终切片。
func len(v Type) int
len() 函数用于获取任何参数的长度。它以一个参数作为我们希望找到其长度的数据类型变量，并返回整数值，即变量的长度。
算法
步骤 1 - 创建一个 NewHeap 函数，该函数创建一个带有空数组的新堆。创建一个将元素作为输入的 Insert 方法
步骤 2 - 在第一步中，将新元素附加到数组的末尾。使用新插入元素的索引调用 siftUp 方法
步骤 3 - siftUp 方法将索引作为输入，并将元素向上移动到堆中，直到到达正确位置
步骤 4 - 然后，使用 (index - 1) / 2 计算父元素的索引。检查当前索引是否大于 0，并且父元素的值是否大于当前元素
步骤 5 - 如果满足上述条件，则交换父元素和当前元素。使用父元素索引更新索引。然后，重新计算父元素索引
步骤 6 - 在主函数中，使用 NewHeap() 创建一个新堆对象。创建要添加到堆的值列表
步骤 7 - 遍历值列表并使用 Insert 方法将它们插入到堆中，然后使用 fmt 包中的 Println 方法在控制台上打印堆元素
示例 1
在此示例中，我们将编写一个 Go 语言程序，通过假设最小堆将元素插入二叉堆中。在这里，我们使用 Insert 方法将元素插入堆中。
package main
import "fmt"
type Heap struct {
array []int
}
func NewHeap() *Heap {
return &Heap{
array: []int{},
}
}
func (h *Heap) Insert(element int) {
h.array = append(h.array, element)
currentIndex := len(h.array) - 1
for currentIndex > 0 {
parentIndex := (currentIndex - 1) / 2
if h.array[parentIndex] <= h.array[currentIndex] {
break
}
h.array[parentIndex], h.array[currentIndex] = h.array[currentIndex], h.array[parentIndex]
currentIndex = parentIndex
}
}
func main() {
heap := NewHeap()
values := []int{60, 90, 40, 70, 20, 80, 10}
for _, value := range values {
heap.Insert(value)
}
fmt.Println("堆元素为:", heap.array)
}
输出
堆元素为:[10 40 20 90 70 80 60]
示例 2
在此示例中，我们将编写一个 Go 语言程序，使用 siftUp 方法在二叉堆中插入一个元素，该方法将元素插入堆的末尾并将它们与父元素进行比较。
package main
import "fmt"
type Heap struct {
array []int
}
func NewHeap() *Heap {
return &Heap{
array: []int{},
}
}
func (h *Heap) Insert(element int) {
h.array = append(h.array, element)
h.siftUp(len(h.array) - 1)
}
func (h *Heap) siftUp(index int) {
parent_index := (index - 1) / 2
for index > 0 && h.array[parent_index] > h.array[index] {
h.array[parent_index], h.array[index] = h.array[index], h.array[parent_index]
index = parent_index
parent_index = (index - 1) / 2
}
}
func main() {
heap := NewHeap()
values := []int{60, 90, 40, 70, 20, 80, 10}
for _, value := range values {
heap.Insert(value)
}
fmt.Println("堆元素为:", heap.array)
}
输出
堆元素为:[10 40 20 90 70 80 60]
结论
在本文中，我们讨论了如何将元素插入二叉堆。这里我们编译并执行了两个示例。在第一个示例中，我们假设了一个最小堆，在第二个示例中，我们使用了 siftUp 方法。二叉堆的一些应用是优先级队列、堆排序、dijkstra 算法等，这些只是 Go 语言中二叉堆的几个示例。
