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

學無先后，達者為師

網站首頁 編程語言 正文

Golang中堆排序的實現_Golang

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

堆排序

堆的概念：

堆是一棵基于數組實現的特殊的完全二叉樹，這棵二叉樹的每個節點的值必須大于或小于它的兩個子節點。大頂堆是每個節點的值必須大于它的兩個子節點，小頂堆則相反。

堆的頂點必定是ta的最大值或最小值

堆在數組中的存儲形式：

滿足完全二叉樹的情況下，數組中的每個元素依次插入堆中。如圖：

堆[9,8,9,8,7,6,4,1,2,0]的存儲形式是這樣的

堆的性質：

假定數組nums的長度為leng

  • 堆的最后一個節點的父節點下標為：leng/2-1

  • 任何一個下標為n的節點的左右子節點下標為：左子節點ln = n*2+1，右子節點rn = n*2+2。前提是ln和rn小于leng-1,即沒有下標溢出，若溢出表明沒有該子節點

從數組到堆的構建：

大頂堆為例：

先將數組以此插入完全二叉樹中，形成一顆完全二叉樹。(這步什么也不用再，看上圖，腦補)

堆的構建是從右往左、自下而上的。從最后一個節點的父節點leng/2-1開始依次遞減。
  • 判斷左右子節點的是否存在
  • 判斷是否需要替換。子節點的值是否大于當前節點的值
  • 如果替換，那么被替換的子節點也要左一次堆的構建

得到個堆

代碼實現

func buildHeep(nums []int, len int) {
	// 找到最后一個節點的父節點
	parent := len/2 - 1
	for parent >= 0 {
		heapify(nums, parent, len)
		parent--
	}
}

func heapify(nums []int, parent, len int) {
	// 判斷兩個子節點是否比父節點大，如果是的話替換
	max := parent
	lson := parent*2 + 1
	rson := parent*2 + 2
	if lson < len && nums[lson] > nums[max] {
		// 左節點是否大于父節點
		max = lson
	}
	if rson < len && nums[rson] > nums[max] {
		// 右節點是否大于父節點
		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]

堆排序：

大頂堆為例：

得到堆之后只能確定一個最值，即頂點是最大值。繼而：

將頂點和最后一個點調換位置，最后一個節點變為最大值

數組下標為0至倒數第二位即最大值前一位，再做一次堆構建，又可以獲得一個最大值

繼續以上步驟，這一次的最后一位是在上一次的基礎上的

將頂點和最后一個點調換位置，最后一個節點變為最大值

數組下標為0至倒數第二位即最大值前一位，再做一次堆構建，又可以獲得一個最大值

直到遍歷到數組長度為2，得到排序后的數組

func HeapSort(nums []int) []int {
	// 堆排序,只能確認第一次個數是最大或最小的
	// 調換第一個元素和最后一個元素位置、從0倒數第二個繼續堆排序
	i := len(nums)
	for i > 1 {
		buildHeep(nums, i)
		swap(&nums[0], &nums[i-1])
		i--
	}

	return nums
}

一行為一次堆疊化

完整代碼：

// heap.go
package structpk

import "fmt"

/*
	給定整數數組nums和k，
	請返回數組中第k個最大元素，
	請注意，你需要找的是數組排序后的第k個最大元素，
	而不是第k個不同的元素
*/
func swap(a, b *int) {
	*a, *b = *b, *a
}

func HeapSort(nums []int) []int {
	// 堆排序,只能確認第一次個數是最大或最小的
	// 調換第一個元素和最后一個元素位置、從0倒數第二個繼續堆排序
	i := len(nums)
	for i > 1 {
		buildHeep(nums, i)
		swap(&nums[0], &nums[i-1])
		i--
	}

	return nums
}
func buildHeep(nums []int, len int) {
	// 找到最后一個節點的父節點
	parent := len/2 - 1
	for parent >= 0 {
		heapify(nums, parent, len)
		parent--
	}
	fmt.Println(nums[0:len])

}

func heapify(nums []int, parent, len int) {
	// 判斷兩個子節點是否比父節點大，如果是的話替換
	max := parent
	lson := parent*2 + 1
	rson := parent*2 + 2
	if lson < len && nums[lson] > nums[max] {
		// 左節點是否大于父節點
		max = lson
	}
	if rson < len && nums[rson] > nums[max] {
		// 右節點是否大于父節點
		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

欄目分類
最近更新