Max Heap - Golang.go

package DataStuctures

import (
	"testing"
)

type MaxHeap struct {
	heap []int
}

func (h *MaxHeap) Push(node int) {
	i := len(h.heap)
	h.heap = append(h.heap, node)
	j := i/2
	for h.heap[j] < h.heap[i] {
		h.heap[j], h.heap[i], i, j = h.heap[i], h.heap[j], j, j/2
	}
}

func (h *MaxHeap) Pop() int {
	var node int
	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 Test_MaxHeap_Push(t *testing.T) {
	testDatas := [] struct{
		values []int
		result []int
	}{
		{
			[]int{35, 33, 12, 16, 25, 34, 10, 45},
			[]int{45, 35, 33, 34, 12, 25, 10, 16},
		},
		{
			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
			[]int{10, 9, 8, 6, 7, 3, 2, 5, 1, 4},
		},
	}

	IsIntArraysEquals := func (a []int, b []int) 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 {

		h := MaxHeap{}

		for _, value := range td.values {
			h.Push(value)
		}

		if !IsIntArraysEquals(h.heap, td.result) {
			t.Errorf("Source: %v \nExpected: %d, \nActual: %d",
				td.values,
				td.result,
				h.heap)
		}
	}
}

func Test_MaxHeap_Pop(t *testing.T) {
	testDatas := [] struct{
		values []int
		result []int
	}{
		{
			[]int{35, 33, 12, 16, 25, 34, 10, 45},
			[]int{45, 35, 34, 33, 25, 16, 12, 10},
		},
		{
			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
			[]int{10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
		},
	}

	for _, td := range testDatas {

		h := MaxHeap{}

		for _, value := range td.values {
			h.Push(value)
		}

		for _, value := range td.result {
			r := h.Pop()
			if value != r {
				t.Errorf("Source: %d \nExpected: %d, \nActual: %d",
					td.values,
					value,
					r)
			}
		}
	}
}