用 Go 来实现链表、栈、队列、散列表、树、二叉树、堆、图
堆的认识
堆是一棵基于数组实现的特殊的完全二叉树，这棵二叉树的每个节点的值必须大于或小于它的两个子节点。大顶堆是每个节点的值必须大于它的两个子节点，小顶堆则相反。
堆的顶点必定是他的最大值或最小值
应用场景
- 优先级队列：合并有序小文件，高性能定时器
- 利用堆求 Top K
- 求中位数
堆
// heap.go
package main
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)
}
}
func main() {
fmt.Println(HeapSort([]int{
3, 5, 3, 0, 8, 6,
}))
}
go run xxx.go
[8 5 6 0 3 3]
[6 5 3 0 3]
[5 3 3 0]
[3 0 3]
[3 0]
[0 3 3 5 6 8]