Golang中堆排序的實現(xiàn)
堆排序
堆的概念：
堆是一棵基于數(shù)組實現(xiàn)的特殊的完全二叉樹，這棵二叉樹的每個節(jié)點的值必須大于或小于它的兩個子節(jié)點。大頂堆是每個節(jié)點的值必須大于它的兩個子節(jié)點，小頂堆則相反。
堆的頂點必定是ta的最大值或最小值
堆在數(shù)組中的存儲形式：
滿足完全二叉樹的情況下，數(shù)組中的每個元素依次插入堆中。如圖：
堆[9,8,9,8,7,6,4,1,2,0]的存儲形式是這樣的
堆的性質：
假定數(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ù)組到堆的構建：
大頂堆為例：
先將數(shù)組以此插入完全二叉樹中，形成一顆完全二叉樹。(這步什么也不用再，看上圖，腦補)
堆的構建是從右往左、自下而上的。從最后一個節(jié)點的父節(jié)點leng/2-1開始依次遞減。
- 判斷左右子節(jié)點的是否存在
- 判斷是否需要替換。子節(jié)點的值是否大于當前節(jié)點的值
- 如果替換，那么被替換的子節(jié)點也要左一次堆的構建
得到個堆
代碼實現(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))
// 結果 ： [8 5 6 0 3 3]堆排序：
大頂堆為例：
得到堆之后只能確定一個最值，即頂點是最大值。繼而：
將頂點和最后一個點調換位置，最后一個節(jié)點變?yōu)樽畲笾?/p>
數(shù)組下標為0至倒數(shù)第二位即最大值前一位，再做一次堆構建，又可以獲得一個最大值
繼續(xù)以上步驟，這一次的最后一位是在上一次的基礎上的
將頂點和最后一個點調換位置，最后一個節(jié)點變?yōu)樽畲笾?/p>
數(shù)組下標為0至倒數(shù)第二位即最大值前一位，再做一次堆構建，又可以獲得一個最大值
直到遍歷到數(shù)組長度為2，得到排序后的數(shù)組
func HeapSort(nums []int) []int {
// 堆排序,只能確認第一次個數(shù)是最大或最小的
// 調換第一個元素和最后一個元素位置、從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ù)是最大或最小的
// 調換第一個元素和最后一個元素位置、從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,
}))
}
到此這篇關于Golang中堆排序的實現(xiàn)的文章就介紹到這了,更多相關Golang 堆排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了Go代碼檢查的推薦工具及使用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-07-07
在Go中,可以通過使用database/sql包的DB類型的Ping方法來檢查數(shù)據(jù)庫連接的可用性,本文通過示例代碼,演示了如何在連接檢查失敗時進行重試,感興趣的朋友一起看看吧2023-10-10
今天通過本文給大家介紹Go 語言 JSON 標準庫的使用小結，包括序列化和反序列化的相關知識，感興趣的朋友跟隨小編一起看看吧2021-10-10
解決golang編譯提示dial tcp 172.217.160.113:443: con
這篇文章主要介紹了解決golang編譯提示dial tcp 172.217.160.113:443: connectex: A connection attempt failed,此問題完美解決，需要的朋友可以參考下2023-02-02
如何通過Golang的container/list實現(xiàn)LRU緩存算法
文章介紹了Go語言中container/list包實現(xiàn)的雙向鏈表,并探討了如何使用鏈表實現(xiàn)LRU緩存,LRU緩存通過維護一個雙向鏈表來管理數(shù)據(jù),確保在插入和刪除操作時能夠以O(1)的平均時間復雜度運行,提供了鏈表的操作和使用場景,并附帶了實現(xiàn)LRU緩存的代碼示例,感興趣的朋友一起看看吧2025-03-03
httprouter?是一個高性能、可擴展的HTTP路由，本文將通過一些簡單的示例為大家講講httprouter?這個強大的?HTTP?路由是如何使用的，感興趣的小伙伴可以了解一下2023-05-05
這篇文章介紹了go語言中的函數(shù)與方法，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
這篇文章主要介紹了Go語言map字典用法,實例分析了map字典的使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-02-02
jwt是?json?web?token的簡稱。go使用jwt目前，主流使用的jwt庫是golang-jwt/jwt。本文就來和大家講講golang-jwt/jwt的具體使用，需要的可以參考一下2023-01-01
橋接模式是一種結構型設計模式，通過橋接模式可以將抽象部分和它的實現(xiàn)部分分離，本文主要介紹了GoLang橋接模式，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2023-01-01