Heap adalah struktur data yang berdasarkan pada complete binary tree, namun direpresentasikan melalui array. Ada dua tipe heap, yaitu
- Min Heap: dimana root node merupakan nilai yang paling besar dibandingkan children node dan berlaku secara recursive pada semua level.
- Max Heap: dimana root node merupakan nilai yang paling kecil dibandingkan children node dan berlaku secara recursive pada semua level.
Sebagai contoh kita hanya akan menggunakan MaxHeap. Disini Kita akan membuat sebuah struct yang diberi nama Heap untuk menyimpan value, dimana akan ada 2 value, yaitu :
- Bucket, yang akan menyimpan array dari data integer
- Size, jumlah nilai yang terdapat dalam array Bucket
package main
type Heap struct {
Bucket []int
Size int
}
func main() {
}
Create New MaxHeap
Setelahnya kita akan membuat fungsi NewMaxHeap, dimana:
- Argument, akan menerima array berisi nilai integer
- Return, akan mendeklarasikan bahwa variable Heap yang akan kita kembalikan merupakan pointer. Tujuan dari menggunakan pointer karena pointer merupakan refference dari memory address, sehingga kita bisa memanipulasi data dan menyimpan state yang telah ada sebelumnya.
Pada fungsi NewMaxHeap, kita akan:
- Membuat variable maxHeap, yang dimana merupakan struct kosong. Penggunaan & atau dereferencing , yaitu untuk memanipulasi lansung data pada memory address pointer tersebut.
- Selanjutnya kita membuat for loop menggunakan range pada input nums, dimana terdapat 2 variable yang dikembalikan yaitu index yang kita ganti dengan underscore, karena tidak kita gunakan dan value yang merupakan nilai pada array tersebut.
package main
type Heap struct {
Bucket []int
Size int
}
func NewMaxHeap(nums []int) *Heap {
maxHeap := &Heap{}
for _, value := range nums {
maxHeap.Insert(value)
}
return maxHeap
}
func main() {
}
Insert MaxHeap
Pada method Insert yang akan menerima argumen nilai integer, kita akan:
- Langsung menggunakan append untuk memasukan nilai tersebut pada array Bucket.
- Setelah itu kita akan melakukan increment menggunakan Size++, sehingga tiap ada nilai yang dimasukan size akan terus bertambah
- Setelah itu kita akan memanggil method heapifyUp yang akan kita buat nanti, untuk mengorganisir kembali urutan pada array.
package main
type Heap struct {
Bucket []int
Size int
}
func NewMaxHeap(nums []int) *Heap {
maxHeap := &Heap{}
for _, value := range nums {
maxHeap.Insert(value)
}
return maxHeap
}
func (m *Heap) Insert(value int) {
m.Bucket = append(m.Bucket, value)
m.Size++
m.heapifyUp()
}
func main() {
}
HeapifyUp MaxHeap
Untuk mendapatkan index parent, kita perlu menguranginya dengan 1 terlebih dahulu dan membagi dengan 2, karena kita menggunakan integer jadi jika nilai yang dibagi contohnya menjadi 0.5 maka akan dibulatkan menjadi 0.
func parentIndex(currentIndex int) int {
return (currentIndex-1)/2
}
Biasanya untuk melakukan swaping kita perlu membuat temporary variable, namun kita bisa mempersingkatnya dengan langsung melakukan swaping seperti ini.
func (m *Heap) swap(current, parent int) {
m.Bucket[current], m.Bucket[parent] = m.Bucket[parent], m.Bucket[current]
}
Method heapifyUp dibuat dengan tujuan untuk mereorganisasi array sehingga nilai yang baru kita masukan berada di posisi yang sesuai atau nilai yang besar berada diatas, nilai yang lebih kecil.
- Dalam method heapifyUp kita perlu membuat variable currentIndex untuk melacak index terakhir dari nilai array yang baru kita masukan tadi,
- Disini akan kita bandingkan dengan nilai currentIndex dan nilai parentIndex yang merupakan parent dari currentIndex, jika nilai currentIndex masih lebih besar loop akan terus berjalan dan melakukan swap terhadap dua nilai tersebut, selanjutnya nilai currentIndex akan menjadi parentIndex
package main
type Heap struct {
Bucket []int
Size int
}
func NewMaxHeap(nums []int) *Heap {
maxHeap := &Heap{}
for _, value := range nums {
maxHeap.Insert(value)
}
return maxHeap
}
func (m *Heap) Insert(value int) {
m.Bucket = append(m.Bucket, value)
m.Size++
m.heapifyUp()
}
func (m *Heap) heapifyUp() {
currentIndex := m.Size-1
for m.Bucket[currentIndex] > m.Bucket[parentIndex(currentIndex)] {
m.swap(currentIndex, parentIndex(currentIndex))
currentIndex = parentIndex(currentIndex)
}
}
func parentIndex(currentIndex int) int {
return (currentIndex-1)/2
}
func (m *Heap) swap(current, parent int) {
m.Bucket[current], m.Bucket[parent] = m.Bucket[parent], m.Bucket[current]
}
func main() {
result := NewMaxHeap([]int{10, 20, 30, 40, 50})
fmt.Println(result)
}
Extract MaxHeap
Selanjutnya kita akan menghapus parent root dari heap atau nilai paling besar dengan menggunakan method Extract().
- Kita mengganti nilai index pertama dengan nilai dari index terakhir
- Lalu disini kita akan menginisialisasi lagi array dengan tidak mengikutsertakan index terakhir, setelah itu kita akan mengurangi Size dari array dan memanggil method heapifyDown()
package main
type Heap struct {
Bucket []int
Size int
}
func NewMaxHeap(nums []int) *Heap {
maxHeap := &Heap{}
for _, value := range nums {
maxHeap.Insert(value)
}
return maxHeap
}
func (m *Heap) Insert(value int) {
m.Bucket = append(m.Bucket, value)
m.Size++
m.heapifyUp()
}
func (m *Heap) Extract() {
m.Bucket[0] = m.Bucket[m.Size-1]
m.Bucket = m.Bucket[:m.Size-1]
m.Size--
m.heapifyDown()
}
func (m *Heap) heapifyUp() {
currentIndex := m.Size-1
for m.Bucket[currentIndex] > m.Bucket[parentIndex(currentIndex)] {
m.swap(currentIndex, parentIndex(currentIndex))
currentIndex = parentIndex(currentIndex)
}
}
func parentIndex(currentIndex int) int {
return (currentIndex-1)/2
}
func (m *Heap) swap(current, parent int) {
m.Bucket[current], m.Bucket[parent] = m.Bucket[parent], m.Bucket[current]
}
func main() {
result := NewMaxHeap([]int{10, 20, 30, 40, 50})
fmt.Println(result)
}
HeapifyDown MaxHeap
Untuk mendapatkan index child left dan right kita akan membuat 2 fungsi :
- leftIndex(), dimana untuk medapatkan index child kita perlu mengkalikan dengan 2 lalu ditambah 1
- rightIndex(), dimana untuk medapatkan index child kita perlu mengkalikan dengan 2 lalu ditambah 2
func leftIndex(currentIndex int) int {
return currentIndex*2+1
}
func rightIndex(currentIndex int) int {
return currentIndex*2+2
}
Disini kita akan membuat 5 variable, yaitu
- currentIndex, untuk index yang akan dilalui
- lastIndex, untuk index terakhir pada array
- leftNode, merupakan anak bagian kiri pada currentIndex
- rightNode, merupakan anak bagian kanan pada currentIndex
- childToCompare, merupakan index sementara yang akan kita simpan
Selanjutnya kita memerlukan while loop dimana akan terus berjalan ketika leftNode lebih kecil atau sama dengan leftNode, lalu kita akan membuat if statement dimana:
- Ketika index leftNode sama dengan index lastIndex, maka nilai index childToCompare akan kita ubah menjadi leftNode
- Ketika nilai leftNode lebih besar dibandingkan nilai rightNode, maka nilai index childToCompare akan kita ubah menjadi leftNode
- Jika 2 skenario diatas tidak terpenuhi. maka nilai index childToCompore akan kita ubah menjadi rightNode
Untuk if statment berikutnya kita akan mengecek jika nilai childToCompare lebih besar dibandingkan nilai currentIndex, maka:
- Kita akan melakukan swap terhadap nilai currentIndex dan childToCompare
- Selanjutnya kita akan melakukan update pada variable currentIndex menjadi childToCompare
- Terakhir kita juga perlu melakukan reassign pada nilai leftNode dan rightNode
package main
import "fmt"
type Heap struct {
Bucket []int
Size int
}
func NewMaxHeap(nums []int) *Heap {
maxHeap := &Heap{}
for _, value := range nums {
maxHeap.Insert(value)
}
return maxHeap
}
func (m *Heap) Insert(value int) {
m.Bucket = append(m.Bucket, value)
m.Size++
m.heapifyUp()
}
func (m *Heap) Extract() {
m.Bucket[0] = m.Bucket[m.Size-1]
m.Bucket = m.Bucket[:m.Size-1]
m.Size--
m.heapifyDown()
}
func (m *Heap) heapifyUp() {
currentIndex := m.Size-1
for m.Bucket[currentIndex] > m.Bucket[parentIndex(currentIndex)] {
m.swap(currentIndex, parentIndex(currentIndex))
currentIndex = parentIndex(currentIndex)
}
}
func (m *Heap) heapifyDown() {
currentIndex := 0
lastIndex := m.Size-1
leftNode, rightNode := leftIndex(currentIndex), rightIndex(currentIndex)
childToCompore := 0
for leftNode <= lastIndex {
if leftNode == lastIndex {
childToCompore = leftNode
} else if m.Bucket[leftNode] > m.Bucket[rightNode] {
childToCompore = leftNode
} else {
childToCompore = rightNode
}
if m.Bucket[currentIndex] < m.Bucket[childToCompore] {
m.swap(currentIndex, childToCompore)
currentIndex = childToCompore
leftNode, rightNode = leftIndex(currentIndex), rightIndex(currentIndex)
} else {
return
}
}
}
func parentIndex(currentIndex int) int {
return (currentIndex-1)/2
}
func leftIndex(currentIndex int) int {
return currentIndex*2+1
}
func rightIndex(currentIndex int) int {
return currentIndex*2+2
}
func (m *Heap) swap(current, parent int) {
m.Bucket[current], m.Bucket[parent] = m.Bucket[parent], m.Bucket[current]
}
func main() {
result := NewMaxHeap([]int{10, 20, 30, 40, 50})
fmt.Println(result)
result.Insert(35)
fmt.Println(result)
result.Extract()
fmt.Println(result)
}
Untuk langkah terakhir, kita akan mengetest secara langsung apa yang telah kita buat di atas, dan untuk log pada monitor akan menjadi seperti dibawah ini.
Log Output MaxHeap
> go run main.go
&{[50 40 20 10 30] 5}
&{[50 40 35 10 30 20] 6}
&{[40 30 35 10 20] 5}
Time Complexity
Worst Case Scenario :
- Insert, pada saat kita melakukan append pada array akan memakan waktu n time, namun ketika kita melakukan heapifyUp akan memakan waktu log n, jadi total waktu yang dibutuhkan adalah n log n untuk inserting
- Extract, sama halnya dengan insert dimana kita menghapus array terakhir dengan cara reassign variable array, setelahnya kita melakukan heapifyDown, jadi total waktu yang dibutuhkan adalah n log n untuk melakukan extract