Documentation
¶
Overview ¶
Package heap provides easy to use MinHeap and MaxHeap implementations https://en.wikipedia.org/wiki/Heap_(data_structure)
Interface methods Insert, Extract, IsEmpty, Size are the ways to interact with heap data structure. The Examples, file example_priority_queue_test.go, demonstrates basic usage
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T constraints.Ordered] interface { // Insert element to the heap Insert(T) // Extract top element from the heap // If heap is empty, the call will panic Extract() T // Peek top element from the heap Peek() T // Size of the heap Size() int // IsEmpty returns true for empty heap, false otherwise IsEmpty() bool }
Heap content type satisfy constraints.Ordered While comparing during heap oparation "<" is used
Example ¶
This example initializes the max heap with slice of ints With < operator as comparison the values are extracted in descending order Any type met by constraints.Ordered can be used for the content of the heap
package main
import (
"fmt"
"github.com/qulia/go-qulia/v2/lib/heap"
)
func main() {
iHeap := heap.NewMaxHeap([]int{3, 7, 4, 4, 1}) // Heap[int]
iHeap.Insert(9)
// Calculate the sum of (rank * val) rank: 1-n
sum := 0
for rank := 1; !iHeap.IsEmpty(); rank++ {
cur := iHeap.Extract()
fmt.Printf("Out: %d\n", cur)
sum += cur * rank
}
fmt.Printf("Sum: %d\n", sum)
}
Output: Out: 9 Out: 7 Out: 4 Out: 4 Out: 3 Out: 1 Sum: 72
func NewMaxHeap ¶
func NewMaxHeap[T constraints.Ordered](input []T) Heap[T]
NewMaxHeap initializes the heap structure from provided slice. Returned heap implements heap properties using <, > operators of type with constraints.Ordered
input: The input slice is cloned and will not be modified by this method. Pass nil as input if you do not have any initial entries
func NewMinHeap ¶
func NewMinHeap[T constraints.Ordered](input []T) Heap[T]
NewMinHeap initializes the heap structure from provided slice. Returned heap implements heap properties using <, > operators of type with constraints.Ordered
input: The input slice is cloned and will not be modified by this method. Pass nil as input if you do not have any initial entries
type HeapFlex ¶
type HeapFlex[T common.Comparer[T]] interface { // Insert element to the heap Insert(T) // Extract top element from the heap // If heap is empty, the call will panic Extract() T // Peek top element from the heap Peek() T // Size of the heap Size() int // IsEmpty returns true for empty heap, false otherwise IsEmpty() bool }
Heap content of any type should implement lib.Comparer interface
Example ¶
This example initializes the heap with list of jobs and pushes another one with Insert method With the provided comparison method Less on the type implementing lib.Comparer[T] depending on the heap type (min/max) the jobs will be extracted in order
package main
import (
"fmt"
"github.com/qulia/go-qulia/v2/lib/heap"
)
func main() {
jobs := []job{
{priority: 4, name: "JobA", department: "DeptA"},
{priority: 1, name: "JobB", department: "DeptA"},
{priority: 0, name: "JobZ", department: "DeptC"},
{priority: 7, name: "JobH", department: "DeptA"},
}
jobMinHeap := heap.NewMinHeapFlex(jobs) // HeapFlex[job]
jobMaxHeap := heap.NewMaxHeapFlex(jobs) // HeapFlex[job]
fj := job{priority: 5, name: "JobJ", department: "DeptX"}
jobMinHeap.Insert(fj)
jobMaxHeap.Insert(fj)
for jobMinHeap.Size() != 0 {
j := jobMinHeap.Extract()
fmt.Printf("Current job (pri, name) (%v, %v)\n", j.priority, j.name)
}
for jobMaxHeap.Size() != 0 {
fmt.Printf("Current job %v\n", jobMaxHeap.Extract())
}
}
type job struct {
priority int
name string
department string
}
func (j job) Compare(other job) int {
return j.priority - other.priority
}
Output: Current job (pri, name) (0, JobZ) Current job (pri, name) (1, JobB) Current job (pri, name) (4, JobA) Current job (pri, name) (5, JobJ) Current job (pri, name) (7, JobH) Current job {7 JobH DeptA} Current job {5 JobJ DeptX} Current job {4 JobA DeptA} Current job {1 JobB DeptA} Current job {0 JobZ DeptC}
func NewMaxHeapFlex ¶
NewMaxHeapFlex initializes the heap structure from provided slice. returned heap implements max heap properties where max value defined by lib.Comparer implementation of the type is at the top of the heap to be extracted first
input: The input slice is cloned and will not be modified by this method. Pass nil as input if you do not have any initial entries
func NewMinHeapFlex ¶
NewMinHeapFlex initializes the heap structure from provided slice returned heap implements min heap properties where min value defined by lib.Comparer implementation of the type is at the top of the heap to be extracted first
input: The input slice is cloned and will not be modified by this method Pass nil as input if you do not have any initial entries
Source Files