极客笔记Golang 使用链表实现二叉堆
二叉堆是一种特殊的基于树的数据结构，满足堆属性，其中每个节点的键要么大于等于（在最大堆中）要么小于等于（在最小堆中）其子节点的键。在这个程序中，我们利用链表来表示二叉堆。
在本文中，我们将学习如何使用链表开发Golang程序来实现二叉堆。我们将使用四种不同的方法，包括单链表、双向链表、自定义节点结构和基于切片的实现，以及相关示例来详细解释概念。
语法
heap.insert(value)
该方法用于向堆数据结构中实现插入操作。
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
在这个示例中，使用双向链表来实现二叉堆。双向链表是一种线性数据结构，每个节点包含一个值和两个指针，一个指向前一个节点，另一个指向下一个节点。这段代码使用双向链表实现了一个二叉堆。Insert方法：通过创建一个新节点，插入一个新的值到二叉堆中。新节点的next指针被设置为当前链表的头节点，并且其prev指针被设置为nil。Delete方法：通过将头指针更新为指向链表中的下一个节点来删除二叉堆中的根元素。Print方法：通过从头节点开始遍历链表，并打印每个节点的值来打印二叉堆的元素。
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)时间复杂度的高效插入和删除操作。它提供了一种灵活和动态的数据结构，用于管理一组具有高效维护堆属性的元素。