Golang 来表示二叉堆

二叉堆是一种基于二叉树的数据结构，用于实现优先级队列和排序算法。在本文章中，我们将编写一个用Go语言表示二叉堆的程序。堆有两种类型：最大堆和最小堆。在最大堆中，节点的值大于或等于其子节点的值，在最小堆中，节点的值小于其子节点的值。

语法

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组切片中添加值。它接受一个或多个参数。第一个参数是我们要添加值的数组，后面跟着要添加的值。函数然后返回包含所有值的最终数组片段。

步骤

• 步骤1 - 创建一个Insert方法，用于向堆中添加值，并调用percolateUp方法。在Insert方法之后实现Delete方法。

• 步骤2 - 如果堆为空，则创建一个panic，并显示”堆为空”，将最小元素存储在一个变量中，然后将根节点替换为堆的最后一个元素，并减小堆的大小。

• 步骤3 - 使用根节点的索引调用percolateDown方法，并实现percolateUp方法，该方法接受一个索引作为输入。

• 步骤4 - 然后，计算给定索引的父节点索引，并交换值，直到当前索引大于0并且该值小于父节点的值。创建percolateDown方法来将索引向下移动堆。

• 步骤5 - 计算当前索引的左子节点和右子节点的索引，然后将最小索引视为当前索引，并在左子节点索引小于当前索引的值时进行更新。

• 步骤6 - 如果最小索引仍然是当前索引，则交换当前索引和最小索引处的值。将当前索引更新为最小索引。

• 步骤7 - 在主函数中，使用NewBinaryHeap函数创建一个BinaryHeap对象。然后，使用Insert()方法向堆中插入元素，并在控制台上打印它们。

• 步骤8 - 使用fmt包的Println()函数在控制台上打印删除后堆的更新元素。

示例

在这个示例中，我们将编写一个Go语言程序，表示二进制堆，我们将使用Binary结构体来引用堆。

package main

import (
   "fmt"
)
type BinaryHeap struct {
   array []int
   size  int
}
func NewBinaryHeap() *BinaryHeap {
   return &BinaryHeap{}
}
func (h *BinaryHeap) Insert(value int) {
   h.array = append(h.array, value)
   h.size++
   h.percolateUp(h.size - 1)
}
func (h *BinaryHeap) Delete() int {
   if h.size == 0 {
      panic("Heap is empty")
   }

   min := h.array[0]
   h.array[0] = h.array[h.size-1]
   h.array = h.array[:h.size-1]
   h.size--
   h.percolateDown(0)

   return min
}

func (h *BinaryHeap) percolateUp(index int) {
   parentIndex := (index - 1) / 2

   for index > 0 && h.array[index] < h.array[parentIndex] {
      h.array[index], h.array[parentIndex] = h.array[parentIndex], h.array[index]
      index = parentIndex
      parentIndex = (index - 1) / 2
   }
}

func (h *BinaryHeap) percolateDown(index int) {
   for {
      leftChildIndex := 2*index + 1
      rightChildIndex := 2*index + 2
      smallestIndex := index

      if leftChildIndex < h.size && h.array[leftChildIndex] < h.array[smallestIndex] {
         smallestIndex = leftChildIndex
      }

      if rightChildIndex < h.size && h.array[rightChildIndex] < h.array[smallestIndex] {
         smallestIndex = rightChildIndex
      }

      if smallestIndex == index {
         break
      }

      h.array[index], h.array[smallestIndex] = h.array[smallestIndex], h.array[index]
      index = smallestIndex
   }
}

func main() {
   heap := NewBinaryHeap()

   heap.Insert(50)
   heap.Insert(30)
   heap.Insert(80)
   heap.Insert(20)
   heap.Insert(10)

   fmt.Println("The Heap elements given here are:", heap.array)
   fmt.Println("The minimum element deleted here is:", heap.Delete())
   fmt.Println("The Heap elements after deletion are:", heap.array)
}

输出

The Heap elements given here are: [10 20 80 50 30]
The minimum element deleted here is: 10
The Heap elements after deletion are: [20 30 80 50]

结论

在本文中，我们讨论了如何在Go语言中表示二叉堆。我们通过使用一个示例编译和执行了表示二叉堆的程序，其中我们使用了BinaryHeap结构体来打印堆元素。