数据结构基础 入门——堆

用 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]

参考资料

www.jianshu.com/p/94f390edd885
www.jb51.net/article/245744.htm

本作品采用《CC 协议》，转载必须注明作者和本文链接