堆算法详解

目录

堆

二叉堆的实现

二叉堆的插入

二叉堆取出堆顶 （extract/delete max）

优先对列 (priority queue)

堆的实现

语言中堆的实现

leadcode 题目堆应用

---

堆

堆是一种高效维护集合中最大或最小元素的数据结构。

大根堆：根节点最大的堆，用于维护和查询max。

小根堆：根节点最小的堆，用于维护和查询min

堆是一棵树，并且满足堆特质：大根堆任意节点的关键码 >= 它所有子节点的关键码 （父>=子）。小根堆任意节点的关键码<=它所有子节点的关键码 (父<=子)

二叉堆除了满足堆的性质外，它还必须是一棵完全二叉树

常见的操作时间复杂度

建堆：O(N)、查询最值（get max/min） O(1) 、插入O(logN)、取出最值 （delete max/min） O(logN)

二叉堆的实现

假设第一个元素存储在索引（下标）为1的位置的话，这个节点计作p，那么它的左孩子的索引下标是 p2, 右孩子的索引下标是2p+1,那么p节点的父节点为p/2（下取整）

假设第一个元素存储在索引（下标）为0的位置的话，这个节点计作p，那么它的左孩子的索引下标是 p2+1, 右孩子的索引下标是2p+2,那么p节点的父节点为(p-1/2)（下取整）

根据这个特点我们可以用一维数组存储二叉堆

二叉堆的插入

新元素一律插入到数组heap 的尾部，这个点设置成p，然后向上进行一次调整 （heapify up）

若此时已经到达根，就停止。若满足堆性质 (heap[p]<=heap[p/2]) 停止，否则交换 heap[p] 和 heap[p/2] 令 p=p/2 继续调整

时间复杂度是 O(logN)

二叉堆取出堆顶 （extract/delete max）

把堆顶（heap[1）和 堆尾 （heap[n]） 交换，删除堆尾部 （删除最后一个元素） 然后从根向下进行一个调整（heapify Down） 每次与左右子节点中较大的一个比较，检查堆性质，不满足则交换，注意判定子节点是否存在 那么时间复杂度是O(logN)

优先对列 (priority queue)

二叉堆是优先队列一种简单、常见的实现，但不是最优实现 理论上二叉堆可以支持O(logN) 删除任意元素，只需要 定位该元素在堆中的节点p（可以通过数值与索引之间建立映射得倒） 与堆尾交换，删除堆尾。从p向上、向下各进行一次调整 不过优先队列并没有提供这个方法 在各语言内置的库中，需要支持删除任意元素时，一般使用有序集合等基于平衡二叉搜索树的实现

堆的实现

type heapList []int
​
func (h *heapList) insertVal(val int) {*h = append(*h, val)h.shiftUp(len(*h) - 1)
}
​
func (h *heapList) shiftUp(index int) {for index >= 0 {pInde := index / 2if (*h)[pInde] > (*h)[index] {(*h)[pInde], (*h)[index] = (*h)[index], (*h)[pInde]}index--}
}
​
func (h *heapList) Pop() int {val := (*h)[0](*h)[0] = (*h)[len(*h)-1]*h = (*h)[:len(*h)-1]h.shiftDown(0)h.shiftUp(len(*h) - 1)return val
}
​
func (h *heapList) shiftDown(index int) {hLen := len(*h) - 1for index <= hLen {iL := index*2 + 1if iL+1 <= hLen && (*h)[iL+1] < (*h)[iL] {iL += 1}if iL <= hLen && (*h)[iL] < (*h)[index] {(*h)[iL], (*h)[index] = (*h)[index], (*h)[iL]}index = iL}
}

语言中堆的实现

type li []int
​
func (l li) Len() int {return len(l)
}
​
func (l li) Swap(i, j int) {l[i], l[j] = l[j], l[i]
}
​
func (l li) Less(i, j int) bool {return l[i] > l[j]
}
​
func (l *li) Push(val interface{}) {*l = append(*l, val.(int))
}
​
func (l *li) Pop() interface{} {len_l := len(*l)val := (*l)[len_l-1](*l) = (*l)[:len_l-1]return val
}
​
func main() {var list = &li{}heap.Init(list)heap.Push(list, 1)heap.Push(list, 100)heap.Push(list, 50)heap.Push(list, 150)fmt.Println(heap.Pop(list))fmt.Println(heap.Pop(list))fmt.Println(heap.Pop(list))
}

leadcode 题目堆应用

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/type heapList []*ListNode
​func (t *heapList) insertNode(node *ListNode){*t = append(*t,node)t.shiftup(len(*t)-1)}
​func (t *heapList) shiftup(index int){for index>=0{pIndex:=index/2if (*t)[pIndex].Val>(*t)[index].Val{(*t)[pIndex],(*t)[index] = (*t)[index],(*t)[pIndex]}index--}}
​func (t *heapList) Pop() *ListNode{val:=(*t)[0](*t)[0] = (*t)[len(*t)-1]*t = (*t)[:len(*t)-1]t.ShiftDown(0)t.shiftup(len(*t)-1)return val}
​func (t *heapList) ShiftDown(index int){hLen:=len(*t)-1for index<=hLen{Lindex:=2*index+1if Lindex+1<=hLen && (*t)[Lindex].Val>(*t)[Lindex+1].Val{Lindex+=1}if Lindex<=hLen && (*t)[Lindex].Val<(*t)[index].Val{(*t)[Lindex],(*t)[index] = (*t)[index],(*t)[Lindex]}index = Lindex}}
​
func mergeKLists(list []*ListNode) *ListNode {heap:= &heapList{}for _,v:=range list{if v==nil{continue}heap.insertNode(v)}head:=&ListNode{}temp:=headfor len(*heap)>0{node:=heap.Pop()temp.Next = nodetemp = temp.Nextif node.Next!=nil{heap.insertNode(node.Next)}}return head.Next
}