heap

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, include a job priority queue implementation using MinHeap

Index

• type Interface
  • func NewMaxHeap(input []interface{}, orderFunc lib.OrderFunc) Interface
  • func NewMinHeap(input []interface{}, orderFunc lib.OrderFunc) Interface
• type MaxHeap
• type MinHeap

Examples

• MinHeap

Types

type Interface

type Interface interface {
	// Insert element to the heap
	Insert(interface{})

	// Extract top element from the heap
	Extract() interface{}

	// Size of the heap
	Size() int

	// IsEmpty returns true for empty heap, false otherwise
	IsEmpty() bool
}

func NewMaxHeap

func NewMaxHeap(input []interface{}, orderFunc lib.OrderFunc) Interface

NewMaxHeap initializes the heap structure from provided slice

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

compareToFunc: function that takes two entries and returns positive value if first > second, negative value if first < second, 0 otherwise

func NewMinHeap

func NewMinHeap(input []interface{}, orderFunc lib.OrderFunc) Interface

compareToFunc: function that takes two entries and returns positive value if first > second, negative value if first < second, 0 otherwise

type MaxHeap

type MaxHeap struct {
}

MinHeap is heap structure with max element is top

type MinHeap

type MinHeap struct {
}

MinHeap is heap structure with min element is top

Example

This example initializes the heap with list of jobs and pushes another one with Insert method With the provided comparison method, the jobs with low priority ones are extracted first

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

import (
	"fmt"

	"github.com/qulia/go-qulia/lib"

	"github.com/qulia/go-qulia/lib/heap"
)

type job struct {
	priority   int
	name       string
	department string
}

var (
	jobCompFunc = func(first, second interface{}) int {
		firstJob := first.(job)
		secondJob := second.(job)
		return lib.IntCompFunc(firstJob.priority, secondJob.priority)
	}
)

// This example initializes the heap with list of jobs and pushes another one with Insert method
// With the provided comparison method, the jobs with low priority ones are extracted first
func main() {
	jobs := []interface{}{
		job{
			priority:   4,
			name:       "JobA",
			department: "DeptA",
		},
		job{
			priority:   1,
			name:       "JobB",
			department: "DeptA",
		},
		job{
			priority:   0,
			name:       "JobZ",
			department: "DeptC",
		},
		job{
			priority:   7,
			name:       "JobH",
			department: "DeptA",
		},
	}

	jobHeap := heap.NewMinHeap(jobs, jobCompFunc)

	jobHeap.Insert(job{
		priority:   5,
		name:       "JobJ",
		department: "DeptX",
	})

	for jobHeap.Size() != 0 {
		fmt.Printf("Current job %v\n", jobHeap.Extract().(job))
	}

}

Output:

Current job {0 JobZ DeptC}
Current job {1 JobB DeptA}
Current job {4 JobA DeptA}
Current job {5 JobJ DeptX}
Current job {7 JobH DeptA}