2021-10-21 17:04:38

堆排序算法,堆Top-N问题

堆排序算法,Top-N问题

完整代码

  • 新建文件
  • 复制粘贴
  • 运行代码

效果截图

测试数据

  • nums := []int{3, 1, 2, 5, 7, 8, 5, 4, 6, 9, 2, 6, 8, 3}
  • 测试大数据
func NewData(ln int) []int {
	nums := make([]int, 0, ln)
	for i := 0; i < ln; i++ {
		nums = append(nums, rand.Intn(ln*2))
	}
	return nums
}

运行结果

image.png

代码

package main

import (
	"fmt"
	"log"
	"math/rand"
)

func main() {
	nums := []int{3, 1, 2, 5, 7, 8, 5, 4, 6, 9, 2, 6, 8, 3}
	log.Println("测试", nums)
	headSort(nums)
	log.Println("堆排", nums)
	// TOP N
	k := 10
	nums = NewData(k * 50)
	topNums := nums[:k]
	minHeap(topNums)
	for _, val := range nums[k:] {
		if val > topNums[0] {
			topNums[0] = val
			minHeap(topNums)
		}
	}
	fmt.Println(topNums)
}

func NewData(ln int) []int {
	nums := make([]int, 0, ln)
	for i := 0; i < ln; i++ {
		nums = append(nums, rand.Intn(ln*2))
	}
	return nums
}

func headSort(nums []int) {
	if len(nums) == 0 {
		return
	}
	for i := 0; i < len(nums); i++ {
		minHeap(nums[i:])
	}
}
func minHeap(nums []int) {
	lens := len(nums)
	max := lens/2 - 1
	for i := max; i >= 0; i-- {
		left := i*2 + 1
		right := i*2 + 2
		if left < lens && nums[i] > nums[left] {
			nums[i], nums[left] = nums[left], nums[i]
		}
		if right < lens && nums[i] > nums[right] {
			nums[i], nums[right] = nums[right], nums[i]
		}
	}
}

本文链接:https://blog.zxysilent.com/post/heap-sort-top-n.html

-- EOF --

Comments