structures

Documentation

Index

• type HeapItemItf
  • func GetLargestNItems(inputChan <-chan HeapItemItf, topN int) ([]HeapItemItf, error)
  • func GetSmallestNItems(inputChan <-chan HeapItemItf, topN int) ([]HeapItemItf, error)
  • func GetTopKItems(inputChan <-chan HeapItemItf, topN int, isHighest bool) ([]HeapItemItf, error)
• type HeapItemQ
• type Item
  • func (it *Item) GetKey() interface{}
  • func (it *Item) GetPriority() int
• type PriorityQ
  • func NewPriorityQ(isHighPriority bool, topN int) *PriorityQ
  • func (p *PriorityQ) Len() int
  • func (p *PriorityQ) Less(i, j int) bool
  • func (p *PriorityQ) Pop() (popped interface{})
  • func (p *PriorityQ) Push(x interface{})
  • func (p *PriorityQ) Swap(i, j int)

Examples

• GetLargestNItems
• GetSmallestNItems

Types

type HeapItemItf

type HeapItemItf interface {
	GetKey() interface{}
	GetPriority() int
}

HeapItemItf items need to sort

func GetLargestNItems

func GetLargestNItems(inputChan <-chan HeapItemItf, topN int) ([]HeapItemItf, error)

GetLargestNItems get N highest priority items

Example

package main

import (
	"fmt"

	"github.com/Laisky/go-utils/structures"
)

// Item item that need to sort
type Item struct {
	p int
	k interface{}
}

// GetKey get key of item
func (it *Item) GetKey() interface{} {
	return it.k
}

// GetPriority get priority of item
func (it *Item) GetPriority() int {
	return it.p
}

func main() {
	var (
		itemsWaitToSort = structures.HeapItemQ{
			&Item{p: 1},
			&Item{p: 3},
			&Item{p: 55},
			&Item{p: 2},
			&Item{p: 4441},
			&Item{p: 15555},
			&Item{p: 122},
		}
		itemChan = make(chan structures.HeapItemItf)
	)

	go func() {
		for _, item := range itemsWaitToSort {
			itemChan <- item
		}

		close(itemChan)
	}()

	items, err := structures.GetLargestNItems(itemChan, 3)
	if err != nil {
		panic(err)
	}

	for _, item := range items {
		// 15555
		// 4441
		// 112
		fmt.Println(item.GetPriority())
	}
}

func GetSmallestNItems

func GetSmallestNItems(inputChan <-chan HeapItemItf, topN int) ([]HeapItemItf, error)

GetSmallestNItems get N smallest priority items

Example

package main

import (
	"fmt"

	"github.com/Laisky/go-utils/structures"
)

// Item item that need to sort
type Item struct {
	p int
	k interface{}
}

// GetKey get key of item
func (it *Item) GetKey() interface{} {
	return it.k
}

// GetPriority get priority of item
func (it *Item) GetPriority() int {
	return it.p
}

func main() {
	var (
		itemsWaitToSort = structures.HeapItemQ{
			&Item{p: 1},
			&Item{p: 3},
			&Item{p: 55},
			&Item{p: 2},
			&Item{p: 4441},
			&Item{p: 15555},
			&Item{p: 122},
		}
		itemChan = make(chan structures.HeapItemItf)
	)

	go func() {
		for _, item := range itemsWaitToSort {
			itemChan <- item
		}

		close(itemChan)
	}()

	items, err := structures.GetSmallestNItems(itemChan, 3)
	if err != nil {
		panic(err)
	}

	for _, item := range items {
		// 1
		// 2
		// 3
		fmt.Println(item.GetPriority())
	}
}

func GetTopKItems

func GetTopKItems(inputChan <-chan HeapItemItf, topN int, isHighest bool) ([]HeapItemItf, error)

GetTopKItems calculate topN by heap use min-heap to calculates topN Highest items use max-heap to calculates topN Lowest items

type HeapItemQ

type HeapItemQ []HeapItemItf

type Item

type Item struct {
	Priority int
	Key      interface{}
}

Item item that need to sort

func (*Item) GetKey

func (it *Item) GetKey() interface{}

GetKey get key of item

func (*Item) GetPriority

func (it *Item) GetPriority() int

GetPriority get priority of item

type PriorityQ

type PriorityQ struct {
	// contains filtered or unexported fields
}

PriorityQ priority queue based heap

func NewPriorityQ

func NewPriorityQ(isHighPriority bool, topN int) *PriorityQ

NewPriorityQ create new heapq

func (*PriorityQ) Len

func (p *PriorityQ) Len() int

Len get length of items in heapq

func (*PriorityQ) Less

func (p *PriorityQ) Less(i, j int) bool

Less compare two items in heapq

func (*PriorityQ) Pop

func (p *PriorityQ) Pop() (popped interface{})

Pop pop highest priority item

func (*PriorityQ) Push

func (p *PriorityQ) Push(x interface{})

Push push new item into heapq

func (*PriorityQ) Swap

func (p *PriorityQ) Swap(i, j int)

Swap swat two items in heapq