数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Go语言程序：插入元素到二叉堆
将元素插入二叉堆意味着向堆中添加一个额外的元素，同时保持堆的特性。在这篇 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("The Heap elements are:", heap.array)
}
输出
The Heap elements are: [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("The Heap elements are:", heap.array)
}
输出
The Heap elements are: [10 40 20 90 70 80 60]
结论
在本文中，我们讨论了如何将元素插入到二叉堆中。这里我们编译并执行了两个例子。在第一个例子中，我们假设了一个最小堆，在第二个例子中，我们使用了 siftUp 方法。二叉堆的一些应用包括优先队列、堆排序、迪杰斯特拉算法等等，这些只是 Go 语言中二叉堆的几个例子。
157 次浏览
