TopK问题-基于堆排序和快速排序的实现

缘木求鱼的鱼 · · 3187 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

  Top K 问题相信大家在面试过程中,经常被问到,下面就为大家来讲讲两种常见的实现算法。

一. 基于堆排序实现

    1. 思路
        基于数组前K个数生成一个小顶堆,数组剩余元素依次与堆顶数据比较,小于等于堆顶数据时直接舍弃,大于堆顶数据时替换掉堆顶数据,并调整堆结构保证满足小顶堆要求。
    1. 算法优势
        时间复杂度是O(N*logK),不需要将数组一次全部加载到内存中,可以处理海量数据。
    1. 图解


      Top K 小顶堆实现
    1. 代码实现(Golang)
// 小顶堆法,找top k
func TopKByMinHeap(nums []int, k int) []int {
    length := len(nums)
    // 数组长度小于k,直接返回
    if length < k {     
        return nums
    }
        
    // 数组前k个数据取出,并生成小顶堆
    minHeap := make([]int, 0)
    minHeap = append(minHeap, nums[:k]...)
    CreateMinHeap(minHeap)

    // 遍历数组剩余数据,大于堆顶数据时,替换堆顶,重新维护小顶堆
    for i := k; i < length; i++ {
        if nums[i] > minHeap[0] {
            minHeap[0] = nums[i]
            MinHeapify(minHeap, 0, k)
        }
    }

    return minHeap
}

// 自底向上创建小顶堆
func CreateMinHeap(nums []int) {
    length := len(nums)
    for i := length - 1; i >= 0; i-- {
        MinHeapify(nums, i, length)
    }
}

// 维护小顶堆
func MinHeapify(nums []int, posIndex, length int) {
    // 堆左孩子节点index
    leftIndex := 2*posIndex + 1
    // 堆右孩子节点index
    rightIndex := 2*posIndex + 2
    // 当前节点以及左右孩子节点中最小值的index, 初始化为当前节点index
    minIndex := posIndex
    // 左孩子存在并且小于当前节点值时, 最小值index替换为左孩子index
    if leftIndex < length && nums[leftIndex] < nums[minIndex] {
        minIndex = leftIndex
    }
    // 右孩子存在并且小于当前节点值时, 最小值index替换为右孩子index
    if rightIndex < length && nums[rightIndex] < nums[minIndex] {
        minIndex = rightIndex
    }
    // 最小值节点index不等于当前节点时,替换当前节点和其中较小孩子节点值
    if minIndex != posIndex {
        nums[posIndex], nums[minIndex] = nums[minIndex], nums[posIndex]
        MinHeapify(nums, minIndex, length)
    }
}


二. 基于快排实现

    1. 思路
        利用快排的分划函数找到分界点位置K,则前K个数据即所求结果。
    1. 算法优势
        时间复杂度是O(N),对于可以一次性加载到内存的数组效率很高。
    1. 图解


      Top K 快排实现
    1. 代码实现(Golang)

// 快排法,找Top k
func TopKByQuickSort(nums []int, k int) []int {
    length := len(nums)
    // 数组长度小于k,直接返回
    if length < k {
        return nums
    }

    // 数组进行快排,左侧边界
    left := 0
    // 数组进行快排,右侧边界
    right := length
    // 第一次快排后,获取分界点index
    pivotIndex := partition(nums, left, right)
    
    // 循环快排,找到分界点index刚好等于k
    for pivotIndex != k {
        if pivotIndex < k {
            // 分界点index小于k,继续对分界点右侧进行快排,重新获取分界点index
            left = pivotIndex + 1
        } else {
            // 分界点index大于k,缩小快排范围为上次分界点与本次分界点之间数据,重新获取分界点index
            right = pivotIndex
        }
        pivotIndex = partition(nums, left, right)
    }
    return nums[:k]
}

// 按分界点,进行快排,并返回分界点index
func partition(nums []int, left, right int) int {
    // 初始化分界值为左边界值
    pivot := nums[left]
    // 所有大于分界值的数据边界index
    pos := left
    
    // 小于分界值时,边界扩展,将数据替换到边界值index位置,
    for i := left; i < right; i++ {
        if nums[i] > pivot {
            pos++
            nums[i], nums[pos] = nums[pos], nums[i]
        }
    }
    
    // 交换分界值的数据边界index和分界点index,使得分界点左侧均大于分界点,右侧均小于分界点
    nums[pos], nums[left] = nums[left], nums[pos]

    return pos
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:缘木求鱼的鱼

查看原文:TopK问题-基于堆排序和快速排序的实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3187 次点击  
加入收藏 微博
上一篇:谈谈go.sum
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传