資料結構
網路
關係型資料庫管理系統
作業系統
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 函式用於向陣列切片中新增值。它接受多個引數。第一個引數是要新增值的陣列，後面跟著要新增的值。然後，該函式返回包含所有值的最終陣列切片。
func len(v Type) int
len() 函式用於獲取任何引數的長度。它接受一個引數作為我們想要查詢長度的資料型別變數，並返回一個整數，即該變數的長度。
演算法
步驟 1 - 建立一個 NewHeap 函式，它建立一個帶有空陣列的新堆。建立一個 Insert 方法，它以元素作為輸入
步驟 2 - 在第一步中，將新元素追加到陣列的末尾。使用新插入元素的索引呼叫 siftUp 方法
步驟 3 - siftUp 方法以索引作為輸入，並將元素向上移動到堆中，直到它到達正確的位置
步驟 4 - 然後，使用 (index - 1) / 2 計算父節點的索引。檢查當前索引是否大於 0 以及父節點的值是否大於當前元素
步驟 5 - 如果滿足上述條件，則交換父節點和當前元素。使用父節點索引更新索引。然後，重新計算父節點索引
步驟 6 - 在主函式中，使用 NewHeap() 建立一個新的堆物件。建立一個要新增到堆中的值的列表
步驟 7 - 遍歷值的列表，並使用 Insert 方法將它們插入到堆中，並使用 fmt 包中的 Println 方法在控制檯上列印堆元素
示例 1
在這個例子中，我們將編寫一個 Go 語言程式，透過假設最小堆來將元素插入到二叉堆中。在這裡，我們使用 Insert 方法將元素插入到堆中。
package main
import "fmt"
type Heap struct {
array []int
}
func NewHeap() *Heap {
return &Heap{
array: []int{},
}
}
func (h *Heap) Insert(element int) {
h.array = append(h.array, element)
currentIndex := len(h.array) - 1
for currentIndex > 0 {
parentIndex := (currentIndex - 1) / 2
if h.array[parentIndex] <= h.array[currentIndex] {
break
}
h.array[parentIndex], h.array[currentIndex] = h.array[currentIndex], h.array[parentIndex]
currentIndex = parentIndex
}
}
func main() {
heap := NewHeap()
values := []int{60, 90, 40, 70, 20, 80, 10}
for _, value := range values {
heap.Insert(value)
}
fmt.Println("The Heap elements are:", heap.array)
}
輸出
The Heap elements are: [10 40 20 90 70 80 60]
示例 2
在這個例子中，我們將編寫一個 Go 語言程式，使用 siftUp 方法將元素插入到二叉堆中，該方法將元素插入到堆的末尾並將其與父節點進行比較。
package main
import "fmt"
type Heap struct {
array []int
}
func NewHeap() *Heap {
return &Heap{
array: []int{},
}
}
func (h *Heap) Insert(element int) {
h.array = append(h.array, element)
h.siftUp(len(h.array) - 1)
}
func (h *Heap) siftUp(index int) {
parent_index := (index - 1) / 2
for index > 0 && h.array[parent_index] > h.array[index] {
h.array[parent_index], h.array[index] = h.array[index], h.array[parent_index]
index = parent_index
parent_index = (index - 1) / 2
}
}
func main() {
heap := NewHeap()
values := []int{60, 90, 40, 70, 20, 80, 10}
for _, value := range values {
heap.Insert(value)
}
fmt.Println("The Heap elements are:", heap.array)
}
輸出
The Heap elements are: [10 40 20 90 70 80 60]
結論
在本文中，我們討論瞭如何將元素插入到二叉堆中。這裡我們編譯並執行了兩個例子。在第一個例子中，我們假設了一個最小堆，在第二個例子中，我們使用了 siftUp 方法。二叉堆的一些應用包括優先佇列、堆排序、迪傑斯特拉演算法等等，這些只是 Go 語言中二叉堆的幾個例子。
157 次瀏覽
