# 基础

堆的基本操作：

插入
堆化，Sift Up，Sift Down
取出最值

使用数组表示的二叉堆的基本性质：

二叉堆的数组表示

每个结点的左孩子为下标i的2倍：left child(i) = i * 2；每个结点的右孩子为下标i的2倍加1：right child(i) = i * 2 + 1
每个结点的父亲结点为下标的二分之一：parent(i) = i / 2，注意这里是整数除，2和3除以2都为1，大家可以验证一下
注意：这里是把下标为0的地方空出来了的，主要是为了方便理解，如果0不空出来只需要在计算的时候把i值往右偏移一个位置就行了（也就是加1）

# 实现

Go标准库提供了"container/heap"²封装了堆的基本操作。默认最小堆。

可以自定义struct，并重载method：

func Len() int
func Less(i, j int) bool
func Swap(i, j int) bool
func Push(x interface{})
func Pop() interface{}

重载Less为Greater逻辑即可获得最大堆。

# Heapify

# 实践

# 合并K个升序链表

合并K个升序链表

优先队列合并，先顺序push所有链表最小值，在根据堆顶元素push下个值，时间复杂度O(kn * logk)，空间复杂度O(k)

import (
    "container/heap"
    "fmt"
)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNodeHeap []*ListNode

func (h ListNodeHeap) Len() int { return len(h) }
func (h ListNodeHeap) Less(i, j int) bool {
    return h[i].Val < h[j].Val
}

func (h ListNodeHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *ListNodeHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *ListNodeHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n - 1]
    *h = old[0 : n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    var q ListNodeHeap
    for _, nodePtr := range lists {
        if (nodePtr != nil) {
            q = append(q, nodePtr)
        }
    }
    heap.Init(&q)

    head := ListNode{}
    tail := &head
    for len(q) > 0 {
        nodePtr := heap.Pop(&q).(*ListNode)
        tail.Next = nodePtr
        tail = tail.Next
        if nodePtr.Next != nil {
            heap.Push(&q, nodePtr.Next)
        }
    }
    return head.Next
}

其他方法：

遍历插入，时间复杂度为O(k²n)，空间复杂度为O(1)
分治合并，时间复杂度为O(kn * logk)，空间复杂度为O(logk)

# 数组中的第K个最大元素

数组中的第K个最大元素

构建优先队列，并删除k次

其他方法：

快排，取n-k个元素

import (
    "sort"
)

type Array []int

func (a Array) Len() int           { return len(a) }
func (a Array) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Array) Less(i, j int) bool { return a[i] < a[j] }

func findKthLargest(nums []int, k int) int {
    array := Array(nums)
    sort.Sort(array)
    return array[len(nums) - k]
}

# 前K个高频元素

前K个高频元素

map统计，优先队列取前K个值。

type Node struct{
    Num int
    Freq int
}

type IntHeap []*Node

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {
    return h[i].Freq > h[j].Freq
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(*Node))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n - 1]
    *h = old[0 : n-1]
    return x
}

func topKFrequent(nums []int, k int) []int {
    freqs := map[int]int{}
    for _, n := range nums {
        freqs[n]++
    }
    var q IntHeap
    heap.Init(&q)
    for num, freq := range freqs {
        // fmt.Printf("%v, %v\n", num, freq)
        heap.Push(&q, &Node{
            num, freq,
        })
    }
    ret := []int{}
    for i := 0; i < k; i++ {
        ret = append(ret, heap.Pop(&q).(*Node).Num)
    }
    return ret
}

Previous post: 算法基础 - 链表 Next post: 机器学习系统 2-1 - 推理优化总览