Heap structure

package main

import (
	"fmt"

	"golang.org/x/exp/constraints"
)

func NewHeap[T constraints.Ordered](arr []T) *Heap[T] {
	h := Heap[T]{arr: arr}
	h.BuildMaxHeap()
	return &h
}

type Heap[T constraints.Ordered] struct {
	arr []T
}

func (h *Heap[T]) GetSize() int {
	return len(h.arr)
}

func (h *Heap[T]) Left(i uint) int {

	return 2*int(i) + 1
}

func (h *Heap[T]) Right(i uint) int {

	return 2*int(i) + 2
}

func (h *Heap[T]) Parent(i uint) int {

	if int(i) > h.GetSize()-1 {
		return -1
	}
	return (int(i+1) / 2) - 1
}

// O(1)
func (h *Heap[T]) Max() T { return h.arr[0] }

// O(nlogn)
func (h *Heap[T]) Sort() []T {

	var result []T

	for {
		if h.GetSize() == 0 {
			return result
		}

		result = append(result, h.ExtractMax())
	}
}

func (h *Heap[T]) ExtractMax() T {

	if h.GetSize() == 0 {
		var zr T
		return zr
	}

	max := h.arr[0]
	last := h.arr[len(h.arr)-1]

	h.arr = h.arr[:len(h.arr)-1]

	if max == last {
		return max
	}

	h.arr[0] = last
	h.MaxHeapify(0)

	return max
}

func (h *Heap[T]) MaxHeapify(i uint) {
	left := h.Left(i)
	right := h.Right(i)

	largest := h.arr[i]
	largestIndx := i

	if left < h.GetSize() && h.arr[left] > largest {
		largest = h.arr[left]
		largestIndx = uint(left)
	}

	if right < h.GetSize() && h.arr[right] > largest {
		largest = h.arr[right]
		largestIndx = uint(right)
	}

	if largestIndx != i {
		h.arr[i], h.arr[largestIndx] = largest, h.arr[i]
		h.MaxHeapify(largestIndx)
	}
}

func (h *Heap[T]) BuildMaxHeap() {
	lastNodeIndx := h.GetSize() - 1

	for i := lastNodeIndx; i >= 0; i-- {
		h.MaxHeapify(uint(i))
	}
}

func (h *Heap[T]) traversePreOrder(root string, padding string, pointer string, hasRightSibling bool, node uint) string {

	if int(node) > h.GetSize()-1 {
		return root
	}

	hasRight := h.Right(uint(node)) <= h.GetSize()-1

	str := fmt.Sprintf("%s%s%s%v\n", root, padding, pointer, h.arr[node])

	var paddingForBoth string
	if paddingForBoth = fmt.Sprintf("%s%s", padding, "   "); hasRightSibling {
		paddingForBoth = fmt.Sprintf("%s%s", padding, "│  ")
	}

	pointerForRight := "└──"
	var pointerForLeft string
	if pointerForLeft = "├──"; !hasRight {
		pointerForLeft = "└──"
	}
	strLeft := h.traversePreOrder(str, paddingForBoth, pointerForLeft, hasRight, uint(h.Left(node)))
	return h.traversePreOrder(strLeft, paddingForBoth, pointerForRight, false, uint(h.Right(node)))
}

func (h *Heap[T]) PrintFromNode(i uint) {
	fmt.Print(h.traversePreOrder("", "", "", false, i))
}

func (h *Heap[T]) Print() {
	h.PrintFromNode(0)
}

func main() {

	a := []int{10, 1, 23, 43, 12, 1, 34, 100, 34, 54, 243, 54, 32, 2, 4, 5, 502, 400, 324, 234, 456}

	heap := NewHeap(a)
	heap.Print()

	fmt.Println(heap.Max())
	fmt.Println(heap.Sort())
}