这篇文章我们一起来复习一下堆排序,同时做一道经典的堆排序算法题:合并k个有序链表。建议学过堆排序但已经印象模糊的同学读一下。
堆排序算法
堆排序算法是一个在我看来最神奇的排序算法,它的基本原理是把一个数组看成一个完全二叉树,通过交换节点使这棵树保持每个节点都比它的子节点大(小),这样一棵树叫做大顶堆(小顶堆)。
先复习一下完全二叉树吧
还记得完全二叉树和满二叉树的含义吗?
满二叉树就是一个完美的三角形二叉树,除了最后一层叶子结点以外,其他节点全都有两个子节点。
而完全二叉树就是满二叉树的最后一层从右向左丢掉一些节点。
完全二叉树如果根节点从1开始编号,那么编号为x的节点,父节点是n/2,左子节点是2*n。
另外,二叉树的非叶子结点数是 n/2(向下取整,n是节点总数),在完全二叉树中,编号大于n/2的节点都是叶子结点。
堆排序步骤
一起复习一下堆排序的步骤:
1. 建堆
这一步要做的就是把给定数组调整成一个大顶堆,保证每个节点的值都比其所有子节点小。具体建堆步骤后面再说。
2. 堆顶交换
建堆完成后,根结点就是整个堆里面的最大值,这时把这个节点与堆末尾的节点进行交换,将最大值放在最后,其余n-1个节点组成新的堆。
交换堆顶的值
3. 调整堆
第2步之后,堆顶已经不是最大值,需要重新调整为大顶堆,只需与左右两节点中较大的那一个进行交换,并在交换后的子树上递归执行同样的操作,一直到叶子结点。
调整堆
这一步的时间复杂度大约等于树的高度,也就是O(log(n))
调整后,重新回到第2步,不断循环,每次有一个节点完成排序,直到无序部分只剩下一个节点,排序完成。
怎么建堆?
建堆的过程其实就是从下往上调整堆的过程。从最后一个非叶子结点开始(编号n/2),执行调整堆的操作,然后对编号n/2-1的节点调整堆,直到跟节点。
时间复杂度
根据上面的步骤,主要是建堆和堆调整两个步骤需要计算时间复杂度。
- 堆调整
调整一次的时间复杂度是O(log(n)),所有堆调整步骤加起来的时间复杂度是O(nlog(n)) - 建堆
建堆的时间复杂度并不是直觉的O(nlog(n)),因为从底向上的调整过程中,每次调整堆的大小是不同的,经过复杂推导,建堆的时间复杂度是O(n)。
堆的应用场景
堆排序的时间复杂度往往不如快排,但堆这个数据结构却有很多应用场景,最常见的比如优先队列,在外部排序中也有应用。在算法题中,例如找到第k大的数,k个有序链表合并,都需要用到堆。
其实根据上面的时间复杂度分析,堆排序在调整堆这一步只有O(log(n))的时间复杂度,非常快。如果有每次变更一条数据就需要重新排序的场景,就可以考虑能不能使用堆。
算法题:合并k个有序链表
题目不再赘述,leetcode链接:合并k个有序链表
分析
构建一个k个节点组成的小顶堆,每次将堆顶元素放入合并后的链表,并替换为next的节点。如果next是nil,则与最后一个节点交换。然后重建堆。
有序链表组成堆
代码
代码与堆排序的代码十分类似,核心就是堆调整重建的过程,先写出这部分代码:
重建堆
func adjust(heap []*ListNode, i int) {
l := len(heap)
for i < nonLeafCount(l) {
j := leftChild(i)
if j+1 < l && heap[j+1].Val < heap[j].Val {
j++
}
if heap[i].Val <= heap[j].Val {
break
}
swap(heap, i, j)
i = j
}
}
其中用到了nonLeafCount 和 leftChild两个函数还没有实现,含义分别是非叶子节点数,和 左子节点编号,注意这里的编号是从0开始的,与上面的公式中从一开始不同。
func nonLeafCount(length int) int {
return length / 2
}
func leftChild(parentIndex int) int {
return parentIndex * 2 + 1
}
Generator,持续获取最小节点并维护堆
接下来实现generator方法,作用是每次从堆中取出最小节点(堆顶),并维护堆。
维护堆的过程分两种情况:
- 堆顶还有next:将堆顶替换为next节点,并重建堆。
- 堆顶没有next:将堆顶替换为堆的最后一个节点,堆节点数减1,并重建堆。
func generator(heap []*ListNode) (*ListNode, []*ListNode) {
node := heap[0]
if heap[0].Next != nil {
heap[0] = heap[0].Next
} else {
swap(heap, 0, len(heap)-1)
heap = heap[:len(heap)-1]
}
adjust(heap, 0) // don't forget
return node, heap
}
初始化堆
初始化堆的算法与堆排序一致,只要自底向上调整堆即可:
func build(heap []*ListNode) {
for i:=nonLeafCount(len(heap))-1; i>=0; i-- {
adjust(heap, i)
}
}
整体逻辑
最后,通过入口函数将这些函数整合起来。
这里我使用了额外的头指针head。
func mergeKLists(lists []*ListNode) *ListNode {
build(heap)
head := &ListNode{}
last := head
for len(heap) > 0 {
last.Next, heap = generator(heap)
last = last.Next
}
return head.Next
}
边界条件
需要考虑输入节点为nil的情况,这里不再贴了。
AC!
最后,我们的代码打败了95%的Go代码!
结语
关于堆排序,重点需要记忆的是:
- 构建堆和重建堆的步骤,以及他们的时间复杂度;
- 如何根据节点编号找到子节点、最后一个非叶子结点(注意区分跟节点是从0还是从1开始编号);
- 记住堆在优先队列、第k大数等场景都会用到。
网友评论