文章目錄

• 前言
• 正文
• • golang實(shí)現(xiàn)堆的代碼
  • 堆排序
• 總結(jié)

在融安等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)營(yíng)銷推廣,外貿(mào)營(yíng)銷網(wǎng)站建設(shè),融安網(wǎng)站建設(shè)費(fèi)用合理。前言

通過(guò)本篇文章，你將學(xué)會(huì)：

1. 初始化大頂堆
2. 彈出堆頂元素
3. 往堆中插入元素
4. 堆排序

學(xué)習(xí)的前提是你已經(jīng)知道在構(gòu)建好的堆中調(diào)整單個(gè)元素的原理，也就是下沉(down)操作和上浮(up)操作。

正文

在"container/heap"標(biāo)準(zhǔn)庫(kù)中有實(shí)現(xiàn)堆的Init,Pop,Push,Fix等方法，只需要向heap的Init,Pop,Push,Fix等方法中傳入實(shí)現(xiàn)了Interface的結(jié)構(gòu)類型就可以使用heap的方法來(lái)初始化和調(diào)整堆

heap.Interface類型如下

type Interface interface {sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

sort.Interface類型如下

type Interface interface {Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

所以我們的自定義類型需要實(shí)現(xiàn)上面五個(gè)方法

type IntHeap []int

func (h IntHeap) Len() int           {return len(h) }
func (h IntHeap) Swap(i, j int)      {h[i], h[j] = h[j], h[i] }
func (h IntHeap) Less(i, j int) bool {return h[i] >h[j] } // 大頂堆
//func (h IntHeap) Less(i, j int) bool { return h[i]< h[j] } // 小頂堆

func (h *IntHeap) Push(x interface{}) {*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

我們一個(gè)一個(gè)來(lái)解釋type IntHeap []int表明我們底層使用數(shù)組來(lái)存儲(chǔ)堆元素
len()返回IntHeap的長(zhǎng)度
Swap(i, j int)交換IntHeap中下標(biāo)為i和j的元素
Less(i, j int)如果下標(biāo)i的元素“小于”下標(biāo)j的元素，則返回true，否則返回false。返回true則表明i不會(huì)在j的下方。通過(guò)控制Less函數(shù)的返回可以實(shí)現(xiàn)大頂堆或者小頂堆
Push(x any)函數(shù)往IntHeap的末尾插入元素
Pop()函數(shù)取出IntHeap末尾的元素

Pop之所以這樣實(shí)現(xiàn)，是因?yàn)樵趆eap包的源碼中，Pop在調(diào)用IntHeap的Pop之前進(jìn)行了一些操作：
heap.Push函數(shù)會(huì)往堆尾插入元素，如何對(duì)這個(gè)元素進(jìn)行上浮(up)操作
heap.Pop函數(shù)會(huì)先交換堆首和堆尾元素，然后再對(duì)堆首元素進(jìn)行下沉(down)操作，所以我們的IntHeap類型是往堆尾插入的。

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x any) {h.Push(x)
	up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) any {n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

up和down代碼如下

func up(h Interface, j int) {for {i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {	break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {i := i0
	for {j1 := 2*i + 1
		if j1 >= n || j1< 0 {// j1< 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2< n && h.Less(j2, j1) {	j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {	break
		}
		h.Swap(i, j)
		i = j
	}
	return i >i0
}

golang實(shí)現(xiàn)堆的代碼

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           {return len(h) }
func (h IntHeap) Swap(i, j int)      {h[i], h[j] = h[j], h[i] }
func (h IntHeap) Less(i, j int) bool {return h[i] >h[j] } // 大頂堆
//func (h IntHeap) Less(i, j int) bool { return h[i]< h[j] } // 小頂堆

func (h *IntHeap) Push(x interface{}) {*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {h := &IntHeap{6, 1, 5, 3, 8, 7, 2}
	heap.Init(h)
	heap.Push(h, 4)
	for h.Len() >0 {fmt.Printf("%d ", heap.Pop(h))
	}
}

輸出：

8 7 6 5 4 3 2 1

堆排序

只要實(shí)現(xiàn)了下沉操作，就可以通過(guò)對(duì)非葉子節(jié)點(diǎn)進(jìn)行下沉來(lái)初始化堆，通過(guò)將堆首元素彈出并置于堆尾即可實(shí)現(xiàn)堆排序

func HeapSort(values []int) {n := len(values)
	for i := n/2 - 1; i >= 0; i-- {down(values, n, i)
	}
	for i := n - 1; i >= 0; i-- {values[i], values[0] = values[0], values[i]
		down(values, i, 0)
	}
}

func down(values []int, n, i int) {largest := i
	l := 2*i + 1
	r := 2*i + 2
	if l< n && values[l] >values[largest] {largest = l
	}
	if r< n && values[r] >values[largest] {largest = r
	}
	if largest != i {values[i], values[largest] = values[largest], values[i]
		down(values, n, largest)
	}
}

也可以使用heap包來(lái)實(shí)現(xiàn)

func HeapSort2(values []int) {h := IntHeap(values)
	heap.Init(&h)
	n := h.Len()
	for i := 0; i< n; i++ {heap.Pop(&h)
	}
}

測(cè)試HeapSort2

func main() {var nums = []int{6, 1, 5, 3, 8, 7, 2, 4}
	HeapSort2(nums)
	fmt.Println(nums)
}

輸出：

[1 2 3 4 5 6 7 8]

總結(jié)

通過(guò)這篇文章，可以學(xué)會(huì)如何使用heap包來(lái)構(gòu)建和操作堆，并可以實(shí)現(xiàn)堆排序等應(yīng)用。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：golang實(shí)現(xiàn)大頂堆只看這篇文章就夠了-創(chuàng)新互聯(lián)
路徑分享：http://www.rwnh.cn/article32/jogsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、定制開發(fā)、網(wǎng)站策劃、ChatGPT、網(wǎng)站維護(hù)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)