Priority Queues

//PQ

package main

import (
	"fmt"
)

type node struct {
	distance int
	vertex   int
}

type priorityQ struct {
	currentIndex int
	q            []*node
}

func (pq *priorityQ) printPQ() {
	for index := 1; index <= pq.currentIndex; index++ {
		fmt.Printf("index=%d {v:%d, d:%d} \n", index, pq.q[index].vertex, pq.q[index].distance)
	}
	fmt.Println()
}

func (pq *priorityQ) enQueue(vertex, distance int) {
	pq.q[pq.currentIndex].vertex = vertex
	pq.q[pq.currentIndex].distance = distance
	parentIndex := pq.currentIndex / 2
	if parentIndex != 0 {
		pq.minHeapify(parentIndex)
	}
	pq.currentIndex++
}

func (pq *priorityQ) deQueue() {
  //TODO
}

func (pq *priorityQ) minHeapify(parentIndex int) {	
	if pq.q[parentIndex].distance >= pq.q[parentIndex*2].distance {
		pq.q[parentIndex], pq.q[parentIndex*2] = pq.q[parentIndex*2], pq.q[parentIndex]
		if parentIndex/2 != 0 {
			pq.minHeapify(parentIndex / 2)
		}
	} else if pq.q[parentIndex].distance >= pq.q[parentIndex*2+1].distance {
		pq.q[parentIndex], pq.q[parentIndex*2+1] = pq.q[parentIndex*2+1], pq.q[parentIndex]
		if parentIndex/2 != 0 {
			pq.minHeapify(parentIndex / 2)
		}
	}
}

func main() {
	totalVertices := 20
	pq := &priorityQ{
		q:            make([]*node, totalVertices),
		currentIndex: 1,
	}

	for i := 0; i < totalVertices; i++ {
		pq.q[i] = &node{}
	}

	pq.enQueue(1, 10)
	pq.enQueue(2, 9)
	pq.enQueue(3, 8)
	pq.enQueue(4, 7)
	pq.enQueue(5, 6)
	pq.enQueue(6, 5)
	pq.enQueue(7, 4)
	pq.enQueue(8, 3)
	pq.enQueue(9, 2)
	pq.printPQ()

	// expected order of array resentation of heap
	// 2, 3, 5, 4, 8, 9, 6, 10, 7
	// index=1 {v:9, d:2}
	// index=2 {v:8, d:3}
	// index=3 {v:6, d:5}
	// index=4 {v:7, d:4}
	// index=5 {v:3, d:8}
	// index=6 {v:2, d:9}
	// index=7 {v:5, d:6}
	// index=8 {v:1, d:10}
	// index=9 {v:4, d:7}
	// index=10 {v:0, d:0}

}

index=1 {v:9, d:2} 
index=2 {v:8, d:3} 
index=3 {v:6, d:5} 
index=4 {v:7, d:4} 
index=5 {v:3, d:8} 
index=6 {v:2, d:9} 
index=7 {v:5, d:6} 
index=8 {v:1, d:10} 
index=9 {v:4, d:7} 
index=10 {v:0, d:0} 


Program exited.