Kodas

heap.go — karkasas

Sukurk heap.go. Karkasas kaip įprasta; kūnai tavo.

Ką verta pasižymėti:

Peek privalo būti O(1). Jokio ciklo, jokio palyginimo — a[0]. Jei ieškai, dar kartą perskaityk krūvos savybę.
Pop į šaknį kelia paskutinį masyvo elementą, ne vaiką. Antro žingsnio spąstai.
Push lygina su tėvu, Pop — su abiem vaikais. Todėl Pop atlieka apie dvigubai daugiau palyginimų vienam lygiui nei Push.
Sukeitimai nėra palyginimai. c.Hit() kviečiamas tik lyginant įvertinimus; sukeitimai kaupiami į Swaps. Šeštas žingsnis remiasi šiuo skirtumu.
NewMinHeap gauna talpos užuominą ir ja privalo pasinaudoti (make([]Item, 0, capacity)). Iš to gimsta vienas paskirstymas visai struktūrai — skaičius, kurį šeštame žingsnyje statysi prieš 20 020.

`TopKHeap` — kur reikia pagalvoti

TopKHeap naudoja min-krūvą k geriausių elementų, ir čia sukasi visa esmė.

Krūvoje laikai k geriausių iki šiol matytų. Jos mažiausias elementas yra silpniausias iš tų k. Naujas įrašas turi įveikti tik jį:

jei krūvoje mažiau nei k: Push ir toliau
worst ← Peek()
c.Hit()
jei naujas ≤ worst: praleisk        // negali išstumti silpniausio iš k geriausių
Pop(); Push(naujas)

Daugumai įrašų tai vienas palyginimas ir viskas. Todėl kaina yra O(n log k), o ne O(n log n).

Min-krūva „geriausiems" atrodo apversta ir turi taip atrodyti: laikai geriausius, o žiūri į blogiausią iš jų, nes būtent jis pasitraukia pirmas.

Pabaigoje krūva ištuštinama, o rezultatas apverčiamas — Pop duoda mažiausią pirmą, o tau reikia geriausio pirmo.

heap.go SUKURTI

Sukurk šį failą kataloge ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; heap_test.go
// decides whether you got it right.
//
// Every comparison between two RATINGS goes through c.Hit(). Swaps are counted
// separately in Swaps — they are not comparisons, and step 6 is about work the
// counter cannot see.

// MinHeap is a binary heap keyed on Rating, and it is A TREE STORED IN AN ARRAY.
//
// There are no pointers here. For the node at index i:
//
//	parent   (i-1)/2
//	children 2i+1 and 2i+2
//
// Lessons 11 and 12 spent 88 and 96 bytes per node on pointers scattered across
// the heap. This spends 0, in one contiguous slice — which is why its constant
// is small.
type MinHeap struct {
	a     []Item
	Swaps int
}

// NewMinHeap takes a capacity hint. Pre-sizing the slice is why the whole
// structure can be ONE allocation — step 6 measures that against the 20,020 the
// standard library needs for the same work.
func NewMinHeap(capacity int) *MinHeap { panic("not implemented") }

func (h *MinHeap) Len() int { panic("not implemented") }

// Peek returns the minimum without removing it. This must be O(1) — no loop, no
// comparison. If you find yourself searching, re-read the heap property.
func (h *MinHeap) Peek() (Item, bool) { panic("not implemented") }

// Push appends at the end and sifts UP until the parent is no larger.
func (h *MinHeap) Push(it Item, c *metrics.Counter) { panic("not implemented") }

// Pop removes and returns the minimum.
//
// The LAST element of the array moves to the root and sinks. Promoting a child
// instead leaves a hole and breaks the shape — see step 2's gotcha.
func (h *MinHeap) Pop(c *metrics.Counter) (Item, bool) { panic("not implemented") }

// Height is the depth of the array-tree: floor(log2(n)) + 1.
//
// No traversal is needed — the shape is implied by the length alone. Lesson 11
// had to walk the whole tree for this; here there is nothing to walk.
func (h *MinHeap) Height() int { panic("not implemented") }

// IsHeap checks the invariant everywhere: no parent larger than its child. The
// test calls it after every single Push, so keep it simple and correct rather
// than clever.
func (h *MinHeap) IsHeap() bool { panic("not implemented") }

// TopKHeap returns the k highest-rated items, best first, using a MIN-heap of
// size k.
//
// The trick that makes it O(n log k): the heap holds the k best seen so far, and
// its MINIMUM is the weakest of them. A new item only has to beat that one — so
// most items cost a single comparison and are discarded.
//
// It must NOT sort the input, and it must not hold more than k items at a time.
func TopKHeap(items []Item, k int, c *metrics.Counter) []Item {
	panic("not implemented")
}

heap.go — karkasas

TopKHeap — kur reikia pagalvoti

`TopKHeap` — kur reikia pagalvoti