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