“Implementierung von Golang Priority Warteschlange” Code-Antworten

Implementierung von Golang Priority Warteschlange

package main

import (
	"fmt"
	"golang.org/x/exp/constraints"
)

type MinHeap[T constraints.Ordered] struct {
	Items []T
}

func NewMinHeap[T constraints.Ordered]() *MinHeap[T] {
	return &MinHeap[T]{}
}

func getLeftChildIndex(index int) int  { return index*2 + 1 }
func getRightChildIndex(index int) int { return index*2 + 2 }
func getParentIndex(index int) int     { return (index - 1) / 2 }
func (this *MinHeap[T]) hasLeftChild(index int) bool {
	return getLeftChildIndex(index) < len(this.Items)
}
func (this *MinHeap[T]) hasRightChild(index int) bool {
	return getRightChildIndex(index) < len(this.Items)
}
func (this *MinHeap[T]) hasParent(index int) bool { return getParentIndex(index) >= 0 }

func (this *MinHeap[T]) leftChild(index int) T  { return this.Items[getLeftChildIndex(index)] }
func (this *MinHeap[T]) rightChild(index int) T { return this.Items[getRightChildIndex(index)] }
func (this *MinHeap[T]) parent(index int) T     { return this.Items[getParentIndex(index)] }

func (this *MinHeap[T]) swap(indexOne, indexTwo int) {
	this.Items[indexOne], this.Items[indexTwo] = this.Items[indexTwo], this.Items[indexOne]
}

func (this *MinHeap[T]) Peek() T {
	if len(this.Items) == 0 {
		panic("No items to peek")
	}

	return this.Items[0]
}

func (this *MinHeap[T]) Poll() T {
	if len(this.Items) == 0 {
		panic("No items to Poll")
	}

	item := this.Items[0]
	this.Items[0] = this.Items[len(this.Items)-1]
	this.Items = this.Items[:len(this.Items)-1]

	this.HeapifyDown()

	return item
}

func (this *MinHeap[T]) Add(item T) {
	this.Items = append(this.Items, item)
	this.HeapifyUp()
}

func (this *MinHeap[T]) HeapifyUp() {
	index := len(this.Items) - 1

	for this.hasParent(index) && this.parent(index) > this.Items[index] {
		this.swap(getParentIndex(index), index)
		index = getParentIndex(index)
	}
}

func (this *MinHeap[T]) HeapifyDown() {
	index := 0

	for this.hasLeftChild(index) {
		smallerChildIndex := getLeftChildIndex(index)

		if this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index) {
			smallerChildIndex = getRightChildIndex(index)
		}

		if this.Items[index] < this.Items[smallerChildIndex] {
			break
		} else {
			this.swap(index, smallerChildIndex)
			index = smallerChildIndex
		}
	}
}

func main() {
	mm := NewMinHeap[int]()
	mm.Add(10)
	mm.Add(3)
	mm.Add(1)
	mm.Add(2)
	mm.Poll()
	fmt.Println(mm.Peek())
}