golang 最大堆实现排行榜（Top N的排名）

package main

import (
	"fmt"
)

/*
 * 使用最大堆实现排行榜功能（前N名排行榜）
 */

type InfoNode struct {
	UserID int
	Score  int
}

type RankList struct {
	MaxHeap  []InfoNode
	HeapSize int

	UserNode map[int]int
}

func NewRankList() *RankList {
	return &RankList{
		UserNode: make(map[int]int),
	}
}

func (r *RankList) UpdateUserScore(userID int, score int) {
	i, exist := r.UserNode[userID]
	if exist && score != r.MaxHeap[i].Score {
		if score > r.MaxHeap[i].Score {
			r.IncreaseScore(i, score)
		} else {
			r.DecreaseScore(i, score)
		}

	}
}

func (r *RankList) IncreaseScore(i int, score int) {
	if score < r.MaxHeap[i].Score {
		return
	}

	r.MaxHeap[i].Score = score
	for i > 0 && r.MaxHeap[Parent(i)].Score < r.MaxHeap[i].Score {
		r.MaxHeap[Parent(i)], r.MaxHeap[i] = r.MaxHeap[i], r.MaxHeap[Parent(i)]
		r.UserNode[r.MaxHeap[Parent(i)].UserID] = Parent(i)
		r.UserNode[r.MaxHeap[i].UserID] = i

		i = Parent(i)
	}
}

func (r *RankList) DecreaseScore(i int, score int) {
	if score > r.MaxHeap[i].Score {
		return
	}

	r.MaxHeap[i].Score = score
	MaxHeapifyNode(r.MaxHeap, i, r.HeapSize)
}

func (r *RankList) Insert(node InfoNode) {
	r.HeapSize++
	r.MaxHeap = append(r.MaxHeap, node)
	r.IncreaseScore(r.HeapSize-1, node.Score)
}

func (r *RankList) Output() []InfoNode {
	heap := make([]InfoNode, r.HeapSize, r.HeapSize)
	for i := 0; i < r.HeapSize; i++ {
		heap[i] = r.MaxHeap[i]
	}

	heapsize := r.HeapSize
	for i := r.HeapSize - 1; i > 0; i-- {
		heapsize--
		heap[0], heap[i] = heap[i], heap[0]
		MaxHeapifyNode(heap, 0, heapsize)
	}

	return heap
}

func MaxHeapifyNode(A []InfoNode, i, heapsize int) {
	largest := i
	l := Left(i)
	r := Right(i)

	if l < heapsize && A[l].Score > A[largest].Score {
		largest = l
	}

	if r < heapsize && A[r].Score > A[largest].Score {
		largest = r
	}

	if largest != i {
		A[largest], A[i] = A[i], A[largest]
		MaxHeapifyNode(A, largest, heapsize)
	}
}

func main() {
	A := []int{3, 6, 9, 7, 8, 4, 2, 10}
	fmt.Println(A)

	rankList := NewRankList()
	for i, score := range A {
		rankList.Insert(InfoNode{
			UserID: i + 1,
			Score:  score,
		})
	}

	rankList.UpdateUserScore(3, 109)
	rankList.UpdateUserScore(2, 106)
	rankList.UpdateUserScore(8, 1)
	
	B := rankList.Output()
	for i := len(B) - 1; i >= 0; i-- {
		fmt.Println(B[i])
	}
}