minheap_test.go

package heapx

import (
	"math/rand"
	"reflect"
	"sort"
	"testing"
)

func TestPushPop(t *testing.T) {
	h := New[int](0)
	for _, v := range []int{5, 3, 8, 1, 9, 2, 7} {
		h.Push(v)
		if !IsMinHeap(h.Snapshot()) {
			t.Fatalf("not a heap after pushing %d: %v", v, h.Snapshot())
		}
	}
	if v, _ := h.Peek(); v != 1 {
		t.Errorf("Peek = %d", v)
	}

	want := []int{1, 2, 3, 5, 7, 8, 9}
	got := []int{}
	for h.Len() > 0 {
		v, _ := h.Pop()
		got = append(got, v)
	}
	if !reflect.DeepEqual(got, want) {
		t.Errorf("Pop sequence = %v, want %v", got, want)
	}

	if _, ok := h.Pop(); ok {
		t.Error("expected !ok on empty heap")
	}
}

func TestHeapify(t *testing.T) {
	r := rand.New(rand.NewSource(1))
	in := make([]int, 200)
	for i := range in {
		in[i] = r.Intn(1000)
	}

	h := FromSlice(in)
	if !IsMinHeap(h.Snapshot()) {
		t.Fatal("FromSlice did not produce a heap")
	}

	got := []int{}
	for h.Len() > 0 {
		v, _ := h.Pop()
		got = append(got, v)
	}

	want := append([]int(nil), in...)
	sort.Ints(want)

	if !reflect.DeepEqual(got, want) {
		t.Error("popping the heap did not produce sorted order")
	}
}

func TestKSmallest(t *testing.T) {
	in := []int{7, 2, 5, 1, 9, 3, 4, 8, 6}
	got := KSmallest(in, 4)
	want := []int{1, 2, 3, 4}
	if !reflect.DeepEqual(got, want) {
		t.Errorf("KSmallest = %v, want %v", got, want)
	}
	if KSmallest(in, 0) != nil {
		t.Error("k=0 should return nil")
	}
	if got := KSmallest(in, 100); len(got) != len(in) {
		t.Errorf("k > n: returned %d items, want %d", len(got), len(in))
	}
}