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步 − 在main函数中，使用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方法将一个元素插入二叉堆。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语言中的一些示例。