数据结构
网络
关系型数据库管理系统
操作系统
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 函数用于向数组切片添加值。它接受多个参数。第一个参数是要添加值的数组，后面跟着要添加的值。然后，该函数返回包含所有值的最终数组切片。
算法
步骤 1 − 创建一个 Insert 方法向堆中添加值并调用 percolateUp 方法，在 Insert 方法之后实现 Delete 方法。”。
步骤 2 − 如果堆为空，则抛出“堆为空”的异常，将最小元素存储在一个变量中，然后用堆的最后一个元素替换根节点，并减小堆的大小。
步骤 3 − 使用根节点的索引调用 percolateDown 方法，并实现接收索引作为输入的 percolateUp 方法。
步骤 4 − 然后，计算给定索引的父节点索引，并交换值，直到当前索引大于 0 且值小于父节点值。创建 percolateDown 方法将索引向下移动到堆中。
步骤 5 − 计算当前索引的左子节点和右子节点的索引，然后将最小索引视为当前索引，如果左子节点索引小于当前索引处的值，则更新它。
步骤 6 − 如果最小索引仍然是当前索引，则交换当前索引和最小索引处的值。将当前索引更新为最小索引。
步骤 7 − 在 main 函数中，使用 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 结构体来打印堆元素。
362 次浏览
