Created
June 4, 2022 08:28
-
-
Save sychonet/67ec4b1b1e03a8fe88a1bc9563cf5986 to your computer and use it in GitHub Desktop.
Implementation of min heap in Golang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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() | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Try this code on https://go.dev/play/p/eypDVArQLb0