heap.md

Heap

Heap is a binary heap tree implemented by slice.

Source

• https://github.com/duke-git/lancet/blob/main/datastructure/heap/maxheap.go

Usage

import (
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

Index

• MaxHeap
• Push
• Pop
• Peek
• Data
• Size

Documentation

1. MaxHeap

MaxHeap is a binary heap tree implemented by slice, The key of the root node is both greater than or equal to the key value of the left subtree and greater than or equal to the key value of the right subtree.

NewMaxHeap

Return a NewMaxHeap pointer instance.

Signature:

type MaxHeap[T any] struct {
	data       []T
	comparator constraints.Comparator
}
func NewMaxHeap[T any](comparator constraints.Comparator) *MaxHeap[T]

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    fmt.Println(maxHeap)
}

Push

Push value into the heap

Signature:

func (h *MaxHeap[T]) Push(value T)

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}

	for _, v := range values {
		maxHeap.Push(v)
	}

    fmt.Println(maxHeap.Data()) //[]int{12, 9, 11, 4, 8, 10, 7, 1, 3, 5, 6, 2}
}

Pop

Pop return the largest value, and remove it from the heap if heap is empty, return zero value and fasle

Signature:

func (h *MaxHeap[T]) Pop() (T, bool)

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}

	for _, v := range values {
		maxHeap.Push(v)
	}
    val, ok := maxHeap.Pop()

    fmt.Println(val) //12
    fmt.Println(ok) //true
}

Peek

Return the largest element from the heap without removing it, if heap is empty, it returns zero value and false.

Signature:

func (h *MaxHeap[T]) Peek() (T, bool)

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}

	for _, v := range values {
		maxHeap.Push(v)
	}
    val, ok := maxHeap.Peek()

    fmt.Println(val) //12
    fmt.Println(maxHeap.Size()) //12
}

Data

Return all element of the heap

Signature:

func (h *MaxHeap[T]) Data() []T

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}

	for _, v := range values {
		maxHeap.Push(v)
	}

    fmt.Println(maxHeap.Data()) //[]int{12, 9, 11, 4, 8, 10, 7, 1, 3, 5, 6, 2}
}

Size

Return the number of elements in the heap

Signature:

func (h *MaxHeap[T]) Size() int

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2}

	for _, v := range values {
		maxHeap.Push(v)
	}

    fmt.Println(maxHeap.Size()) //3
}

PrintStructure

Print the tree structure of the heap

Signature:

func (h *MaxHeap[T]) PrintStructure()

Example:

package main

import (
    "fmt"
    heap "github.com/duke-git/lancet/v2/datastructure/heap"
)

type intComparator struct{}

func (c *intComparator) Compare(v1, v2 any) int {
	val1, _ := v1.(int)
	val2, _ := v2.(int)

	if val1 < val2 {
		return -1
	} else if val1 > val2 {
		return 1
	}
	return 0
}

func main() {
    maxHeap := heap.NewMaxHeap[int](&intComparator{})
    values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}

	for _, v := range values {
		maxHeap.Push(v)
	}

    fmt.Println(maxHeap.PrintStructure())
//        12
//    9       11
//  4   8   10   7
// 1 3 5 6 2
}