[Go版]算法通关村第十四关白银——堆高效解决的经典问题（在数组找第K大的元素、堆排序、合并K个排序链表）

题目：在数组中找第K大的元素

题目链接：LeetCode-215. 数组中的第K个最大元素

解法1：维护长度为k的最小堆，遍历n-k个元素，逐一和堆顶值对比后，和堆顶交换，最后返回堆顶

复杂度：时间复杂度$O(k+(n-k)logk)$、空间复杂度$O(1)$

Go代码

func findKthLargest(nums []int, k int) int {length := len(nums)if k > length {return -1}makeMinHeap(nums, k)for i:=k;i<length;i++ {if nums[i] > nums[0] {nums[0], nums[i] = nums[i], nums[0]minHeap(nums, 0, k)}}return nums[0]
}func makeMinHeap(arr []int, length int) {// 从最后一个非叶子节点开始for i:=(length/2-1); i>=0; i-- {minHeap(arr, i, length)}
}// 最小堆化
func minHeap(arr []int, i int, length int) {left, right := 2*i+1, 2*i+2min := iif left < length && arr[left] < arr[min] {min = left}if right < length && arr[right] < arr[min] {min = right}if min != i {arr[i], arr[min] = arr[min], arr[i]minHeap(arr, min, length)}
}

解法2：构建长度为n的最大堆，遍历k次，每次删除堆顶，且堆长度-1，最后返回堆顶（k较小时此法更优）

复杂度：时间复杂度$O(n+klogn)$、空间复杂度$O(1)$

Go代码

func findKthLargest(nums []int, k int) int {length := len(nums)if k > length {return -1}// 将nums构建为一个最大堆makeMaxHeap(nums, length)for i:=1; i<k; i++ {nums[0], nums[length-i] = nums[length-i], nums[0]maxHeap(nums, 0, length-i)}return nums[0]
}// 最大堆
func makeMaxHeap(arr []int, length int) {// 第一个非叶子节点for i:=(length/2-1); i>=0; i-- {maxHeap(arr, i, length)}
}
// 最大堆化
func maxHeap(arr []int, i int, length int) {l, r, max := 2*i+1, 2*i+2, iif l<length && arr[l] > arr[max] {max = l}if r<length && arr[r] > arr[max] {max = r}if max != i {arr[max], arr[i] = arr[i], arr[max]maxHeap(arr, max, length)}
}

题目：堆排序

题目链接：LeetCode-912. 排序数组

思路分析：构建长度为n的最大堆，依次删除堆顶并逆序放到数组尾部，且堆长度-1，n-1次后数组则为升序

复杂度：时间复杂度$O(nlog(n))$、空间复杂度$O(1)$

Go代码

func sortArray(nums []int) []int {length := len(nums)if length == 1 {return nums}makeMaxHeap(nums, length)for i:=length-1; i>0; i-- {nums[0], nums[i] = nums[i], nums[0]maxHeap(nums, 0, i)}return nums
}
// 构建最大堆
func makeMaxHeap(nums []int, length int) {// 第一个非叶子结点for i:=length/2-1; i>=0; i-- {maxHeap(nums, i, length)}
}
// 最大堆化
func maxHeap(nums []int, i int, length int) {l, r, max := 2*i+1, 2*i+2, iif l<length && nums[l] > nums[max] {max = l}if r<length && nums[r] > nums[max] {max = r}if max != i {nums[max], nums[i] = nums[i], nums[max]maxHeap(nums, max, length)}
}

题目：合并K个排序链表

题目链接：LeetCode-23. 合并 K 个升序链表

思路分析：维护长度为k的最小堆，依次删除堆顶接到返回链表上（纵向拼接），注意取值时判断空链表

复杂度：时间复杂度$O(k+nlogk)$、空间复杂度$O(1)$

Go代码

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {length := len(lists)if length == 1 {return lists[0]}// 去除空数组for i:=0; i<length; i++ {if lists[i] == nil {lists[i], lists[length-1] = lists[length-1], lists[i]length--i--}}newList := &ListNode{}tmp := newList// 最小化makeMinHeap(lists, length)for length > 0 && lists[0] != nil {// 取出当前最小tmp.Next = &ListNode{Val:lists[0].Val}tmp = tmp.Nextlists[0] = lists[0].Nextif lists[0] == nil {lists[0], lists[length-1] = lists[length-1], lists[0]length--}if length > 0 && lists[0] != nil {minHeap(lists, 0, length)}}return newList.Next
}func makeMinHeap(arr []*ListNode, length int) {for i:=length/2-1; i>=0; i-- {minHeap(arr, i, length)}
}func minHeap(arr []*ListNode, i, length int) {left, right, min := 2*i+1, 2*i+2, iif left<length && arr[left].Val < arr[min].Val {min = left}if right<length && arr[right].Val < arr[min].Val {min = right}if min != i {arr[min], arr[i] = arr[i], arr[min]minHeap(arr, min, length)}
}