欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Golang中堆排序的實現(xiàn)

 更新時間:2022年04月24日 09:55:02   作者:zhijie  
堆是一棵基于數(shù)組實現(xiàn)的特殊的完全二叉樹,本文主要介紹了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。前提是lnrn小于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)文章

  • golang定時器和超時的使用詳解

    golang定時器和超時的使用詳解

    這篇文章主要介紹了golang定時器和超時的使用詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • 淺析Go使用定時器時如何避免潛在的內(nèi)存泄漏陷阱

    淺析Go使用定時器時如何避免潛在的內(nèi)存泄漏陷阱

    這篇文章來和大家一起探討一下Go?中如何高效使用?timer,特別是與select?一起使用時,如何防止?jié)撛诘膬?nèi)存泄漏問題,感興趣的可以了解下
    2024-01-01
  • Go?實現(xiàn)?WebSockets之創(chuàng)建?WebSockets

    Go?實現(xiàn)?WebSockets之創(chuàng)建?WebSockets

    這篇文章主要介紹了Go?實現(xiàn)?WebSockets之創(chuàng)建?WebSockets,文章主要探索?WebSockets,并簡要介紹了它們的工作原理,并仔細研究了全雙工通信,想了解更多相關(guān)內(nèi)容的小伙伴可以參考一下
    2022-04-04
  • golang實現(xiàn)基于channel的通用連接池詳解

    golang實現(xiàn)基于channel的通用連接池詳解

    這篇文章主要給大家介紹了關(guān)于golang實現(xiàn)基于channel的通用連接池的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧。
    2018-02-02
  • 解析Go語言編程中的struct結(jié)構(gòu)

    解析Go語言編程中的struct結(jié)構(gòu)

    這篇文章主要介紹了Go語言編程中的struct結(jié)構(gòu),是Go語言入門學習中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-10-10
  • Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解

    Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解

    這篇文章主要介紹了Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2019-03-03
  • 一起來用GoLand開發(fā)第一個Go程序

    一起來用GoLand開發(fā)第一個Go程序

    當您在編輯器中工作時GoLand 會分析您的代碼,尋找優(yōu)化方法,并檢測潛在和實際問題,下面這篇文章主要給大家介紹了關(guān)于用GoLand開發(fā)第一個Go程序的相關(guān)資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2022-12-12
  • Windows系統(tǒng)中搭建Go語言開發(fā)環(huán)境圖文詳解

    Windows系統(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包的使用

    深入了解Golang網(wǎng)絡(luò)編程Net包的使用

    net包主要是增加?context?控制,封裝了一些不同的連接類型以及DNS?查找等等,同時在有需要的地方引入?goroutine?提高處理效率。本文主要和大家分享下在Go中網(wǎng)絡(luò)編程的實現(xiàn),需要的可以參考一下
    2022-07-07
  • Go設(shè)計模式之策略模式講解和代碼示例

    Go設(shè)計模式之策略模式講解和代碼示例

    策略是一種行為設(shè)計模式,?它將一組行為轉(zhuǎn)換為對象,?并使其在原始上下文對象內(nèi)部能夠相互替換,本文就將通過代碼示例給大家詳細的介紹一下Go的策略模式,需要的朋友可以參考下
    2023-08-08

最新評論