Golang中堆排序的實現(xiàn)
堆排序
堆的概念:
堆是一棵基于數(shù)組實現(xiàn)的特殊的完全二叉樹,這棵二叉樹的每個節(jié)點的值必須大于或小于它的兩個子節(jié)點。大頂堆
是每個節(jié)點的值必須大于它的兩個子節(jié)點,小頂堆
則相反。
堆的頂點必定是ta的最大值或最小值
堆在數(shù)組中的存儲形式:
滿足完全二叉樹的情況下,數(shù)組中的每個元素依次插入堆中。如圖:
堆[9,8,9,8,7,6,4,1,2,0]
的存儲形式是這樣的
堆的性質(zhì):
假定數(shù)組nums
的長度為leng
堆的最后一個節(jié)點的父節(jié)點下標為:
leng/2-1
任何一個下標為
n
的節(jié)點的左右子節(jié)點下標為:左子節(jié)點ln = n*2+1
,右子節(jié)點rn = n*2+2
。前提是ln
和rn
小于leng-1
,即沒有下標溢出,若溢出表明沒有該子節(jié)點
從數(shù)組到堆的構(gòu)建:
大頂堆為例:
先將數(shù)組以此插入完全二叉樹中,形成一顆完全二叉樹。(這步什么也不用再,看上圖,腦補)
堆的構(gòu)建是從右往左、自下而上的。從最后一個節(jié)點的父節(jié)點leng/2-1
開始依次遞減。
- 判斷左右子節(jié)點的是否存在
- 判斷是否需要替換。子節(jié)點的值是否大于當前節(jié)點的值
- 如果替換,那么被替換的子節(jié)點也要左一次堆的構(gòu)建
得到個堆
代碼實現(xiàn)
func buildHeep(nums []int, len int) { // 找到最后一個節(jié)點的父節(jié)點 parent := len/2 - 1 for parent >= 0 { heapify(nums, parent, len) parent-- } } func heapify(nums []int, parent, len int) { // 判斷兩個子節(jié)點是否比父節(jié)點大,如果是的話替換 max := parent lson := parent*2 + 1 rson := parent*2 + 2 if lson < len && nums[lson] > nums[max] { // 左節(jié)點是否大于父節(jié)點 max = lson } if rson < len && nums[rson] > nums[max] { // 右節(jié)點是否大于父節(jié)點 max = rson } if parent != max { swap(&nums[max], &nums[parent]) heapify(nums, max, len) } } nums :=[]int{3, 5, 3, 0, 8, 6} buildHeep(nums,len(nums)) // 結(jié)果 : [8 5 6 0 3 3]
堆排序:
大頂堆為例:
得到堆之后只能確定一個最值,即頂點是最大值。繼而:
將頂點和最后一個點調(diào)換位置,最后一個節(jié)點變?yōu)樽畲笾?/p>
數(shù)組下標為0至倒數(shù)第二位即最大值前一位,再做一次堆構(gòu)建,又可以獲得一個最大值
繼續(xù)以上步驟,這一次的最后一位是在上一次的基礎(chǔ)上的
將頂點和最后一個點調(diào)換位置,最后一個節(jié)點變?yōu)樽畲笾?/p>
數(shù)組下標為0至倒數(shù)第二位即最大值前一位,再做一次堆構(gòu)建,又可以獲得一個最大值
直到遍歷到數(shù)組長度為2,得到排序后的數(shù)組
func HeapSort(nums []int) []int { // 堆排序,只能確認第一次個數(shù)是最大或最小的 // 調(diào)換第一個元素和最后一個元素位置、從0倒數(shù)第二個繼續(xù)堆排序 i := len(nums) for i > 1 { buildHeep(nums, i) swap(&nums[0], &nums[i-1]) i-- } return nums }
一行為一次堆疊化
完整代碼:
// heap.go package structpk import "fmt" /* 給定整數(shù)數(shù)組nums和k, 請返回數(shù)組中第k個最大元素, 請注意,你需要找的是數(shù)組排序后的第k個最大元素, 而不是第k個不同的元素 */ func swap(a, b *int) { *a, *b = *b, *a } func HeapSort(nums []int) []int { // 堆排序,只能確認第一次個數(shù)是最大或最小的 // 調(diào)換第一個元素和最后一個元素位置、從0倒數(shù)第二個繼續(xù)堆排序 i := len(nums) for i > 1 { buildHeep(nums, i) swap(&nums[0], &nums[i-1]) i-- } return nums } func buildHeep(nums []int, len int) { // 找到最后一個節(jié)點的父節(jié)點 parent := len/2 - 1 for parent >= 0 { heapify(nums, parent, len) parent-- } fmt.Println(nums[0:len]) } func heapify(nums []int, parent, len int) { // 判斷兩個子節(jié)點是否比父節(jié)點大,如果是的話替換 max := parent lson := parent*2 + 1 rson := parent*2 + 2 if lson < len && nums[lson] > nums[max] { // 左節(jié)點是否大于父節(jié)點 max = lson } if rson < len && nums[rson] > nums[max] { // 右節(jié)點是否大于父節(jié)點 max = rson } if parent != max { swap(&nums[max], &nums[parent]) heapify(nums, max, len) } }
// main.go: package main import ( "demo/structpk" "fmt" ) func main() { fmt.Println(structpk.HeapSort([]int{ 3, 5, 3, 0, 8, 6, })) }
到此這篇關(guān)于Golang中堆排序的實現(xiàn)的文章就介紹到這了,更多相關(guān)Golang 堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Go?實現(xiàn)?WebSockets之創(chuàng)建?WebSockets
這篇文章主要介紹了Go?實現(xiàn)?WebSockets之創(chuàng)建?WebSockets,文章主要探索?WebSockets,并簡要介紹了它們的工作原理,并仔細研究了全雙工通信,想了解更多相關(guān)內(nèi)容的小伙伴可以參考一下2022-04-04golang實現(xiàn)基于channel的通用連接池詳解
這篇文章主要給大家介紹了關(guān)于golang實現(xiàn)基于channel的通用連接池的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧。2018-02-02Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解
這篇文章主要介紹了Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-03-03Windows系統(tǒng)中搭建Go語言開發(fā)環(huán)境圖文詳解
GoLand?是?JetBrains?公司推出的商業(yè)?Go?語言集成開發(fā)環(huán)境(IDE),這篇文章主要介紹了Windows系統(tǒng)中搭建Go語言開發(fā)環(huán)境詳解,需要的朋友可以參考下2022-10-10深入了解Golang網(wǎng)絡(luò)編程Net包的使用
net包主要是增加?context?控制,封裝了一些不同的連接類型以及DNS?查找等等,同時在有需要的地方引入?goroutine?提高處理效率。本文主要和大家分享下在Go中網(wǎng)絡(luò)編程的實現(xiàn),需要的可以參考一下2022-07-07