日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

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

作者：zhijie ? 更新時間： 2022-06-22 編程語言

堆排序

堆的概念：

堆是一棵基于數(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,
	}))
}

原文鏈接：https://juejin.cn/post/7089443841178075167

欄目分類
最近更新