Skip to content

Instantly share code, notes, and snippets.

@sychonet
Created June 4, 2022 08:28
Show Gist options
  • Save sychonet/67ec4b1b1e03a8fe88a1bc9563cf5986 to your computer and use it in GitHub Desktop.
Save sychonet/67ec4b1b1e03a8fe88a1bc9563cf5986 to your computer and use it in GitHub Desktop.
Implementation of min heap in Golang
// Min Heap implementation
// We will be performing following operations on the min heap
// a) Add a new element (add)
// b) Fetch top element (peek)
// c) Delete top element (pop)
package main
import "fmt"
type minHeap struct {
// Create a complete binary tree using an array
// Then use the binary tree to construct a Heap
heap []int
// the number of elements is needed when instantiating an array
// heapSize records the size of the array
heapSize int
// realSize records the number of elements in the Heap
realSize int
}
func (this *minHeap) initialize(size int) {
this.heapSize = size + 1
this.heap = make([]int, this.heapSize)
// To better track the indices of the binary tree,
// we will not use the 0-th element in the array heap
}
func (this *minHeap) add(element int) {
this.realSize++
// If the number of elements in the Heap exceeds the preset heapSize
// print "Added too many elements" and return
if this.realSize >= this.heapSize {
fmt.Println("Added too many elements!")
this.realSize--
return
}
// Add the element into the array
this.heap[this.realSize] = element
// Index of the newly added element
index := this.realSize
// Parent node of the newly added element
// Note if we use an array to represent the complete binary tree
// and store the root node at index 1
// index of the parent node of any node is [index of the node / 2]
// index of the left child node is [index of the node * 2]
// index of the right child node is [index of the node * 2 + 1]
parent := index / 2
// If the newly added element is smaller than its parent node,
// its value will be exchanged with that of the parent node
for this.heap[index] < this.heap[parent] && index > 1 {
temp := this.heap[index]
this.heap[index] = this.heap[parent]
this.heap[parent] = temp
index = parent
parent = index / 2
}
}
// Get the top element of the Heap
func (this *minHeap) peek() int {
return this.heap[1]
}
// Delete the top element of the Heap
func (this *minHeap) pop() int {
// If the number of elements in the current Heap is 0,
// print "Don't have any elements" and return a default value
if this.realSize < 1 {
fmt.Println("Don't have any element!")
return 0
} else {
// When there are still elements in the Heap
// realSize >= 1
removedElement := this.heap[1]
// Put the last element in the Heap to the top of Heap
this.heap[1] = this.heap[this.realSize]
this.realSize--
index := 1
// When the deleted element is not a leaf node
for index <= this.realSize/2 {
// the left child of the deleted element
left := index * 2
// the right child of the deleted element
right := (index * 2) + 1
// If the deleted element is larger than the left or right child
// its value needs to be exchanged with the smaller value
// of the left and right child
if this.heap[index] > this.heap[left] || this.heap[index] > this.heap[right] {
if this.heap[left] < this.heap[right] {
temp := this.heap[left]
this.heap[left] = this.heap[index]
this.heap[index] = temp
index = left
} else {
// this.heap[left] >= this.heap[right]
temp := this.heap[right]
this.heap[right] = this.heap[index]
this.heap[index] = temp
index = right
}
} else {
break
}
}
return removedElement
}
}
func (this *minHeap) print() {
if this.realSize == 0 {
fmt.Println("No element!")
} else {
var output []int
for i := 1; i <= this.realSize; i++ {
output = append(output, this.heap[i])
}
fmt.Println(output)
}
}
// return the number of elements in the Heap
func (this *minHeap) size() int {
return this.realSize
}
func main() {
var h minHeap
h.initialize(3)
h.add(1)
h.add(2)
h.add(3)
// [1,2,3]
h.print()
// 1
fmt.Println(h.peek())
// 1
fmt.Println(h.pop())
// 2
fmt.Println(h.pop())
// 3
fmt.Println(h.pop())
// No element
h.print()
// [4]
h.add(4)
// [5,4]
h.add(5)
// [10,4,5]
h.add(10)
// Added too many elements!
h.add(11)
// [10,4,5]
h.print()
}
@sychonet
Copy link
Author

sychonet commented Jun 4, 2022

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment