数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用链表实现二叉堆的 Golang 程序
二叉堆是一种专门的基于树的数据结构，它满足堆属性，其中每个节点的键要么大于或等于（在最大堆中），要么小于或等于（在最小堆中）其子节点的键。在本程序中，我们使用链表来表示二叉堆。
在这篇文章中，我们将学习如何开发使用链表实现二叉堆的 Golang 程序。在这里，我们将使用四种不同的方法：单链表、双链表、自定义节点结构体和基于切片的实现，并结合示例来阐述这个概念。
语法
heap.insert(value)
此方法用于实现向堆数据结构插入操作。
值 - 需要插入到堆中的值。
heap.delete()
此方法用于从堆中删除顶部元素，即有时是最小元素或最大元素，具体取决于堆的类型。
示例 1
在单链表中，每个节点都有一个指向下一个节点的单个引用，最后一个节点指向 null，表示列表的末尾。列表中的第一个节点称为头部，它是访问列表的入口点。此代码使用单链表实现二叉堆。插入方法：通过创建一个具有给定值的新节点并将它的下一个指针设置为列表的当前头部来将新值插入到二叉堆中。删除方法：通过更新头部指针使其指向列表中的下一个节点来从二叉堆中删除根元素，从而有效地删除当前头部。打印方法：通过从头部节点开始遍历链表并打印每个节点的值来打印二叉堆的元素。
package main
import (
"fmt"
)
type Node struct {
value int
next *Node
}
type Heap struct {
head *Node
}
func (h *Heap) Insert(value int) {
newNode := &Node{
value: value,
next: h.head,
}
h.head = newNode
}
func (h *Heap) Delete() {
if h.head == nil {
return
}
h.head = h.head.next
}
func (h *Heap) Print() {
current := h.head
for current != nil {
fmt.Printf("%d ", current.value)
current = current.next
}
fmt.Println()
}
func main() {
heap := &Heap{}
heap.Insert(10)
heap.Insert(20)
heap.Insert(30)
heap.Insert(40)
fmt.Println("Elements in the binary heap:")
heap.Print()
heap.Delete()
fmt.Println("Elements after deleting from the binary heap:")
heap.Print()
}
输出
Elements in the binary heap: 40 30 20 10 Elements after deleting from the binary heap: 30 20 10
示例 2
在此示例中，使用双链表实现二叉堆。双链表是一种线性数据结构，其中每个节点包含一个值和两个指针，一个指向前一个节点，另一个指向下一个节点。此代码使用双链表实现二叉堆。插入方法：通过创建一个具有给定值的新节点来将新值插入到二叉堆中。新节点的 next 指针设置为列表的当前头部，其 prev 指针设置为 nil。删除方法：通过更新头部指针使其指向列表中的下一个节点来从二叉堆中删除根元素打印方法：通过从头部节点开始遍历链表并打印每个节点的值来打印二叉堆的元素。
package main
import (
"fmt"
)
type Node struct {
value int
prev *Node
next *Node
}
type Heap struct {
head *Node
}
func (h *Heap) Insert(value int) {
newNode := &Node{
value: value,
prev: nil,
next: h.head,
}
if h.head != nil {
h.head.prev = newNode
}
h.head = newNode
}
func (h *Heap) Delete() {
if h.head == nil {
return
}
h.head = h.head.next
if h.head != nil {
h.head.prev = nil
}
}
func (h *Heap) Print() {
current := h.head
for current != nil {
fmt.Printf("%d ", current.value)
current = current.next
}
fmt.Println()
}
func main() {
heap := &Heap{}
heap.Insert(10)
heap.Insert(20)
heap.Insert(30)
heap.Insert(40)
fmt.Println("Elements in the binary heap:")
heap.Print()
heap.Delete()
fmt.Println("Elements after deleting from the binary heap:")
heap.Print()
}
输出
Elements in the binary heap: 40 30 20 10 Elements after deleting from the binary heap: 30 20 10
示例 3
此代码使用基于切片的实现来实现二叉堆。这种使用基于切片的实现的二叉堆实现提供了高效的插入和删除操作，最坏情况下的时间复杂度为 O(log N)，其中 N 是堆中元素的数量。heapifyUp 和 heapifyDown 函数确保在每次操作后都保持堆属性。
package main
import (
"fmt"
)
type Heap struct {
array []int
}
func (h *Heap) Insert(value int) {
h.array = append(h.array, value)
h.heapifyUp(len(h.array) - 1)
}
func (h *Heap) Delete() {
if len(h.array) == 0 {
return
}
h.array[0] = h.array[len(h.array)-1]
h.array = h.array[:len(h.array)-1]
h.heapifyDown(0)
}
func (h *Heap) Print() {
fmt.Println(h.array)
}
func (h *Heap) heapifyUp(index int) {
parent := (index - 1) / 2
for index > 0 && h.array[index] > h.array[parent] {
h.array[index], h.array[parent] = h.array[parent], h.array[index]
index = parent
parent = (index - 1) / 2
}
}
func (h *Heap) heapifyDown(index int) {
n := len(h.array)
largest := index
left := 2*index + 1
right := 2*index + 2
if left < n && h.array[left] > h.array[largest] {
largest = left
}
if right < n && h.array[right] > h.array[largest] {
largest = right
}
if largest != index {
h.array[index], h.array[largest] = h.array[largest], h.array[index]
h.heapifyDown(largest)
}
}
func main() {
heap := &Heap{}
heap.Insert(10)
heap.Insert(20)
heap.Insert(30)
heap.Insert(40)
fmt.Println("Elements in the binary heap:")
heap.Print()
heap.Delete()
fmt.Println("Elements after deleting from the binary heap:")
heap.Print()
}
输出
Elements in the binary heap: [40 30 20 10] Elements after deleting from the binary heap: [30 10 20]
结论
总之，这里我们提供了不同的方法来表示和操作二叉堆数据结构，例如单链表、双链表、自定义节点结构体和基于切片的实现。通过使用链表实现二叉堆，该程序提供了高效的插入和删除操作，时间复杂度为 O(log n)。它为管理元素集合提供了一个灵活且动态的数据结构，并且能够有效地维护堆属性。
435 次浏览
