資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
