Min Heap - Golang.go

package DataStuctures

import (
	"testing"
)

type MinHeap struct {
	 heap []int32
}

func (h *MinHeap) Push(data int32) {
	i := len(h.heap)
	h.heap = append(h.heap, data)

	if i > 0 {
		pi := (i-1)/2

		for h.heap[pi] > h.heap[i] {
			h.heap[pi], h.heap[i], i, pi =  h.heap[i], h.heap[pi], pi, (pi-1)/2
		}
	}
}

func (h *MinHeap) Pop() int32 {
	var node int32
	if len(h.heap) > 0 {
		node = h.heap[0]

		h.heap[0] = h.heap[len(h.heap) - 1]
		h.heap = h.heap[:len(h.heap) - 1]

		var i, il, ir  int
		var ml bool
		var mr bool

		for {

			il = i*2 + 1
			ir = i*2 + 2
			ml = len(h.heap) > il
			mr = len(h.heap) > ir

			if ml {
				if h.heap[il] < h.heap[i] {
					if mr {
						if h.heap[il] <= h.heap[ir] {
							h.heap[il], h.heap[i], i = h.heap[i], h.heap[il], il
							continue
						}
					} else {
						h.heap[il], h.heap[i] , i = h.heap[i], h.heap[il] , il
						continue
					}
				}
			}

			if mr {
				if h.heap[ir] < h.heap[i] {
					if ml {
						if h.heap[ir] <= h.heap[il] {
							h.heap[ir], h.heap[i], i  = h.heap[i], h.heap[ir], ir
							continue
						}
					} else {
						h.heap[ir], h.heap[i], i  = h.heap[i], h.heap[ir], ir
						continue
					}
				}
			}

			return node
		}
	}

	return node
}

func (h *MinHeap) Size() int {
	return len(h.heap)
}

func Test_MinHeap_Push(t *testing.T) {
	testDatas := []struct {
		arr []int32
		result []int32
	} {
		{
			[]int32 {4, 8, 2, 1, 6, 5, 3},
			[]int32 {1, 2, 3, 8, 6, 5, 4},
		},
		{
			[]int32 {3,1,6,5,2, 4},
			[]int32 {1, 2, 4, 5, 3, 6},
		},
	}

	 IsInt32ArraysEquals := func(a []int32, b []int32) bool {
		 if len(a) != len(b) {
			 return false
		 }
		 for i, v := range a {
			 if v != b[i] {
				 return false
			 }
		 }
		 return true
	 }

	for _, td := range testDatas {

		mh := MinHeap{}
		for _, v := range td.arr {
		 	mh.Push(v)
		}

		if !IsInt32ArraysEquals(mh.heap, td.result) {
			t.Errorf("Source: %d \n Expected: %d, Actual: %d",
				td.arr,
				td.result,
				mh.heap)
		}
	}
}

func Test_MinHeap_Pop(t *testing.T) {
	testDatas := []struct {
		arr []int32
		result []int32
	} {
		{
			  []int32 {4, 8, 2, 1, 6, 5, 3},
			[]int32 {1, 2, 3, 4, 5, 6, 8},
		},
		{
			  []int32 {3, 1, 6, 5, 2, 4},
			[]int32 {1, 2, 3, 4, 5, 6},
		},
	}

	for _, td := range testDatas {

		mh := MinHeap{}
		for _, v := range td.arr {
			mh.Push(v)
		}

		for _, v := range td.result {
			r := mh.Pop()
			if r != v {
				t.Errorf("Source: %d \n Expected: %d, Actual: %d",
					mh.heap[0 : mh.Size()],
					v,
					r)
			}
		}
	}
}