Implementation of priority queue using heap data structure (without using golang heap interface)

golang - priority queue using heap

package main

import (
	"encoding/json"
	"fmt"
)

type Queue []int
var n int

func (q *Queue) createMaxHeap() {
	l := len(*q)

	for i := l/2 - 1; i >= 0; i-- {
		q.heapify(i)
	}
}

func (q *Queue) heapify(i int) {
	largest := i
	l := 2*i + 1
	r := 2*i + 2

	if l < n && (*q)[l] > (*q)[i] {
		largest = l
	}

	if r < n && (*q)[r] > (*q)[largest] {
		largest = r
	}

	if i != largest {
		// swap them
		temp := (*q)[largest]
		(*q)[largest] = (*q)[i]
		(*q)[i] = temp

		// heapify the changed child tree
		q.heapify(largest)
	}
}

func (q *Queue) add(v int) {
	i := n
	*q = append(*q, v)
	
	child := i
	parent := (i - 1) / 2

	for {
		if child == 0 {
			break

		} else if (*q)[parent] > (*q)[child] {
			break
			
		} else {
			tmp := (*q)[parent]
			(*q)[parent] = (*q)[child]
			(*q)[child] = tmp

			child = parent
			parent = (child - 1) / 2
		}
	}
	
	n++
}

func (q *Queue) pop() int {
	l := len(*q)
	
	tmp := (*q)[0]
	(*q)[0] = (*q)[l-1]
	(*q)[l-1] = tmp
	
	*q = (*q)[:(n-1)]
	
	n--
	q.heapify(0)
	
	
	return tmp
}

func main() {
	var q Queue = []int{0, 4, 10, 3, 5, 1, 3, 11, 6, 12, 7}
	n = len(q)
	p := &q

	p.createMaxHeap()

	// add element into queue, // complexity : logn
	(&q).add(13)
	
	js, _ := json.Marshal(q)
	fmt.Printf("%v \n", string(js))

	// pop the top element,, complexity : logn
	maxElement := (&q).pop()
	fmt.Printf("maxElement %v \n", maxElement)
}