heap

package main

import (
	"fmt"

	"github.com/jba/heap"
)

func main() {
	type intWithIndex struct {
		value int
		index int
	}

	h := heap.NewIndexed(func(a, b *intWithIndex) int {
		return a.value - b.value
	}, func(v *intWithIndex, i int) { v.index = i })

	item1 := &intWithIndex{value: 5}
	item2 := &intWithIndex{value: 3}
	item3 := &intWithIndex{value: 7}

	h.Init([]*intWithIndex{item1, item2, item3})

	// Get the current min.
	fmt.Println(h.Min().value)

	// Modify item1's value (currently 5, make it smaller).
	item1.value = 1

	// Call Changed to restore heap invariant.
	h.Changed(item1.index)

	// Now item1 should be the new minimum.
	fmt.Println(h.Min().value)

}

Output:

3
1

package main

import (
	"fmt"

	"github.com/jba/heap"
)

func main() {
	type intWithIndex struct {
		value int
		index int
	}

	h := heap.NewIndexed(func(a, b *intWithIndex) int {
		return a.value - b.value
	}, func(v *intWithIndex, i int) { v.index = i })

	item1 := &intWithIndex{value: 5}
	item2 := &intWithIndex{value: 3}
	item3 := &intWithIndex{value: 7}
	item4 := &intWithIndex{value: 1}

	h.Init([]*intWithIndex{item1, item2, item3, item4})

	// Delete specific items by their index.
	h.Delete(item1.index)
	h.Delete(item2.index)

	// Remaining elements.
	for v := range h.Drain() {
		fmt.Println(v.value)
	}

}

Output:

1
7

package main

import (
	"cmp"
	"fmt"

	"github.com/jba/heap"
)

func main() {
	// To implement heapsort, first build a heap, then drain it.
	h := heap.New(cmp.Compare[int])
	h.Init([]int{7, 2, 9, 1, 5})
	for v := range h.Drain() {
		fmt.Println(v)
	}

}

Output:

1
2
5
7
9

package main

import (
	"fmt"

	"github.com/jba/heap"
)

func main() {
	// Create a max-heap using a custom comparison function.
	h := heap.New(func(a, b int) int {
		// Reverse the comparison for max-heap.
		return b - a
	})

	h.Init([]int{5, 3, 7, 1})

	// Extract maximum values.
	fmt.Println(h.TakeMin()) // "Min" extracts the element that compares smallest
	fmt.Println(h.TakeMin())

}

Output:

7
5

This example creates a priority queue with some items, adds and manipulates an item, and then removes the items in priority order.

// This example demonstrates a priority queue built using the heap package.
package main

import (
	"cmp"
	"fmt"

	"github.com/jba/heap"
)

// An Item is something we manage in a priority queue.
type Item struct {
	value    string // The value of the item; arbitrary.
	priority int    // The priority of the item in the queue.
	// The index is needed by update and is maintained by the heap.
	index int // The index of the item in the heap.
}

// This example creates a priority queue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func main() {
	// Create a priority queue with highest priority first.
	// Since Heap is a min-heap, we reverse the comparison.
	pq := heap.NewIndexed(func(a, b *Item) int {
		return cmp.Compare(b.priority, a.priority)
	}, func(item *Item, i int) { item.index = i })

	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Add the items to the priority queue.
	for value, priority := range items {
		pq.Insert(&Item{
			value:    value,
			priority: priority,
		})
	}

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	pq.Insert(item)

	// Change the item's priority.
	item.priority = 5
	pq.Changed(item.index)

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := pq.TakeMin()
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
}

Output:

05:orange 04:pear 03:banana 02:apple

ExampleHeap_topK demonstrates finding the K largest elements using a min-heap and ChangeMin. This is the "top K" algorithm.

package main

import (
	"cmp"
	"fmt"

	"github.com/jba/heap"
)

func main() {
	// To find the K largest elements, use a min-heap of size K.
	// The heap's min is the smallest of the K largest seen so far.
	const K = 3
	data := []int{7, 2, 9, 1, 5, 8, 3, 6, 4, 10}

	h := heap.New(cmp.Compare[int])
	// Initialize the heap with the first K elements.
	// The heap will own data[:K], but we don't need to refer to that
	// part of the slice any more.
	h.Init(data[:K])

	// For remaining elements, replace the min if we find a larger value.
	for _, v := range data[K:] {
		if v > h.Min() {
			h.ChangeMin(v)
		}
	}

	// Drain the heap to get the K largest (in ascending order).
	fmt.Printf("%d largest elements:\n", K)
	for v := range h.Drain() {
		fmt.Println(v)
	}

}

Output:

3 largest elements:
8
9
10