golang priority queue implementation

Priority Queue Implementation in Go (Golang)

A priority queue is a data structure that allows for efficient retrieval of the element with the highest priority. In Go, we can implement a priority queue using a heap data structure.

Define the PriorityQueue struct: We start by defining a struct type called PriorityQueue that represents our priority queue. It will have a slice field to store the elements and a field to keep track of the number of elements in the queue.

go type PriorityQueue struct { elements []int count int }

Implement the Push method: The Push method is used to insert an element into the priority queue. We add the element to the end of the slice and then call the siftUp function to maintain the heap property.

```go func (pq *PriorityQueue) Push(element int) { // Add the element to the end of the slice pq.elements = append(pq.elements, element) pq.count++

   // Restore the heap property
   pq.siftUp(pq.count - 1)

} ```

Implement the Pop method: The Pop method is used to remove and return the element with the highest priority from the priority queue. We swap the first and last elements of the slice, remove the last element, and then call the siftDown function to maintain the heap property.

```go func (pq *PriorityQueue) Pop() int { // Swap the first and last elements pq.swap(0, pq.count-1)

   // Remove the last element
   element := pq.elements[pq.count-1]
   pq.elements = pq.elements[:pq.count-1]
   pq.count--

   // Restore the heap property
   pq.siftDown(0)

   return element

} ```

Implement the siftUp method: The siftUp method is used to restore the heap property after inserting an element. It compares the element with its parent and swaps them if necessary until the heap property is satisfied.

```go func (pq *PriorityQueue) siftUp(index int) { parent := (index - 1) / 2

   if pq.elements[parent] > pq.elements[index] {
       pq.swap(parent, index)
       pq.siftUp(parent)
   }

} ```

Implement the siftDown method: The siftDown method is used to restore the heap property after removing an element. It compares the element with its children and swaps it with the smaller child if necessary until the heap property is satisfied.

```go func (pq PriorityQueue) siftDown(index int) { left := 2index + 1 right := 2*index + 2 smallest := index

   if left < pq.count && pq.elements[left] < pq.elements[smallest] {
       smallest = left
   }
   if right < pq.count && pq.elements[right] < pq.elements[smallest] {
       smallest = right
   }

   if smallest != index {
       pq.swap(smallest, index)
       pq.siftDown(smallest)
   }

} ```

Implement the swap method: The swap method is a helper function used to swap two elements in the slice.

go func (pq *PriorityQueue) swap(i, j int) { pq.elements[i], pq.elements[j] = pq.elements[j], pq.elements[i] }

Usage example: Here's an example of how to use the PriorityQueue implementation:

```go func main() { pq := PriorityQueue{}

   pq.Push(3)
   pq.Push(1)
   pq.Push(4)
   pq.Push(2)

   fmt.Println(pq.Pop()) // Output: 1
   fmt.Println(pq.Pop()) // Output: 2
   fmt.Println(pq.Pop()) // Output: 3
   fmt.Println(pq.Pop()) // Output: 4

} ```

In this example, we create a new PriorityQueue and push elements with different priorities into it. We then use the Pop method to retrieve the elements in ascending order of priority.

That's it! You now have a basic understanding of how to implement a priority queue in Go using a heap data structure.