Go LeetCode

Leetcode 215 Kth Largest Element in an Array

大根堆

Posted by Sirin on October 10, 2025

大根堆

除了快速排序、归并排序之外，一个比较常见的更加灵活的排序方式是堆排序。特别是在215. Kth Largest Element in an Array一题中，堆排和快速选择算法都是非常出色的解决方法。

那么堆排是如何实现的呢？

其核心思想是将数组看作一棵二叉树，保证二叉树的父节点大于其左右子树内的左右节点，从而构建起一个大根堆（如果是小于，那么就是小根堆）。对于节点idx如果其有左右儿子，那么左儿子lChild = 2*idx+1，右儿子rChild = 2*idx+2。堆排的核心思想就是自底向上，将最大的数移动到父结点上，使之局部满足上述要求，通过递归的方式构建起一个堆。

堆的初始化

// 初始化大根堆
func buildMaxHeap(nums []int, heapSize int) {
    // nums是待堆化的数组 heapSize是堆的大小(通常是len(nums))
    // 自底向上进行堆化
    for i := heapSize/2 - 1; i >= 0; i-- {
        maxHeapify(nums, i, heapSize)
    }
    /*
    	这里解释一下为什么是heapSize/2-1
    	因为是自底向上，我们要从最后一个非叶子节点开始进行堆化，
    	而对于最后一个非叶子节点的下标idx，
    	其右儿子最大为2*idx+2 = heapSize
    	故相应的最后一个非叶子节点的下标就是heapSize/2 - 1
    */
}

堆化函数

// 堆化函数
func maxHeapify(nums []int, idx, heapSize int) {
    largest := idx	// 默认最大的节点是当前父节点
    leftChild := idx*2+1	// 左儿子
    rightChild := idx*2+2 	// 右儿子
    
    // 第一个条件检验该节点是否存在
    // 第二个条件检验是否需要更新堆
    if leftChild < heapSize && nums[leftChild] > nums[largest] {
        largest = leftChild
    }
    
    if rightChild < heapSize && nums[rightChild] > nums[largest] {
        largest = rightChild
    }
    
    // 假如需要更新当前堆的父节点
    if largest != idx {
        // 说明左右儿子中有一个比父节点大
        // 交换更新父节点和儿子节点
        nums[idx], nums[largest] = nums[largest], nums[idx]
        // 交换后，此时idx作为父节点有最大值, largest指针移动到了子节点
        // 需要继续向下递归，保证正确性
        maxHeapify(nums, largest, heapSize)
    }
    
}

找到第k个元素

func findKthElement(nums []int) int {
	heapSize := len(nums)	// 初始的堆大小(因为会pop，所以堆大小会变化)
	n := len(nums)	// 数组大小
	buildMaxHeap(nums, heapSize)	//建堆
	// 弹出前k-1个元素
	for i := n-1; i >= n-k+1; i-- {
		// 通过交换+缩容的方式pop掉最大的元素
		// 1. 将最大的元素放入最后一个叶子节点
		// 2. 缩容，弹出该叶子节点
		// 3. 重新进行堆化
		nums[0], nums[i] = nums[i], nums[0]
		heapSize--	
		maxHeapify(nums, 0, heapSize)
	}
	return nums[0]
}

小细节

这里要说明一下go中关于函数传参什么时候应该传引用的问题：

直接传入即可修改：
- 切片 ([]T)
- 映射 (map[K]V)
- 通道 (chan T)
- 函数 (func())
- 接口 (interface{})
需要传入指针才能修改：
- 所有基本类型 (int, float64, string, bool等)
- 数组 ([N]T)
- 结构体 (struct)
记忆技巧：
- 如果类型包含底层数据指针（切片、映射、通道），直接传值即可修改内容
- 如果类型直接包含数据本身，需要传指针才能修改