Implementujte získanie top-5 služieb v O(N) pomocou pomocnej štruktúry

Na získanie najlepších 5 služieb v O(N) môžete použiť dátovú štruktúru nazývanú "min-heap" (min-heap) s pevnou veľkosťou 5. Myšlienka je prejsť všetky služby raz a udržiavať v halde aktuálnych 5 najlepších podľa požadovaného kritéria (napríklad počet požiadaviek alebo hodnotenie).

Príklad v Go:

package main

import (
	"container/heap"
	"fmt"
)

type Service struct {
	Name  string
	Score int
}

type MinHeap []Service

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Score < h[j].Score }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Service))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[0 : n-1]
	return item
}

func Top5Services(services []Service) []Service {
	h := &MinHeap{}
	heap.Init(h)

	for _, s := range services {
		if h.Len() < 5 {
			heap.Push(h, s)
		} else if s.Score > (*h)[0].Score {
			heap.Pop(h)
			heap.Push(h, s)
		}
	}

	// Výsledok v halde, môže byť zoradený v zostupnom poradí
	result := make([]Service, h.Len())
	for i := len(result) - 1; i >= 0; i-- {
		result[i] = heap.Pop(h).(Service)
	}
	return result
}

func main() {
	services := []Service{
		{"A", 10}, {"B", 50}, {"C", 30}, {"D", 40}, {"E", 20}, {"F", 60}, {"G", 15},
	}
	top5 := Top5Services(services)
	for _, s := range top5 {
		fmt.Println(s.Name, s.Score)
	}
}

Týmto spôsobom prejdeme pole iba raz (O(N)) a udržiavame v štruktúre maximálne 5 prvkov, čo je efektívne z hľadiska času a pamäti.