復(fù)盤:
Max Heap 最大堆實(shí)現(xiàn)
優(yōu)化了shiftDown的判斷減少了重復(fù)代碼 , 在遍歷中做部分邊界條件終止
shiftDown 邊界定義出錯(cuò) , 正確的應(yīng)該是該元素沒有左右child后終止
shiftUp的代碼也可以優(yōu)化一些減少代碼重復(fù)判斷 , 而且邊界條件其實(shí)也沒定義好
pesudo code :
// 0 1 2 3 4 5
[2,9,8,5,1,7] 從0開始 , 某個(gè)節(jié)點(diǎn)的parent=(i-1)/2 , leftP=2i+1 rightP=2i+2
MaxHeap {
data []int
size int initial 0 //沒有c++的那些helper function , 額外添加一個(gè)變量存儲(chǔ)size
}
size() {
return t.size
}
isEmpty() {
return data.size==0
}
getParentIndex(index) {
if index==0 //root節(jié)點(diǎn)沒parent node
panic()
return (i-1)/2
}
getLeftIndex(index) {
return 2i+1
}
getRightIndex(index) {
return 2i+2
}
//put into arr last , then shift up
add(value) {
append(data,value)
t.size++
newValueIndex = t.size-1
t.shiftUp(newValueIndex)
}
// if parent less than current , swap , then repeat until root
shiftUp(index) {
parent=t.getParentIndex(index)
for parent!=0 { // 優(yōu)化,小于的時(shí)候就停止了,不需要一直遍歷到root
if data[index]>data[parent] {
swap
}
index=parent
parent=t.getParentIndex(index)
}
}
// store data[0] which is max , then swap last value with data[0] , execute shiftDown at zero idnex
extractMax() {
max=data[0]
data[0]=data[t.size()-1]
t.size-- // soft delete
t.shiftDown(0)
}
swap(v1,v2) {
tmp=v1
v1=v2
v2=tmp
}
1
3 2
// main concern is to find another bigger num float to top
// find biggest from [left,right] , if current less than it , swap , until current bigger than the biggest
shiftDown(index) {
//優(yōu)化了一遍,去除了重復(fù)代碼
for index.leftChild<t.size-1 // 排除沒有child的情況
//find leftindex , right index
leftIndex = t.leftChild(index)
rightIndex= t.rightChild(index)
//find biggest
if t.data[leftIndex]>t.data[rightIndex]
bV=left
bI=leftIndex
if current>bV {
break
}
swap(data[index],biggest)
index=biggestIndex
}
最大堆
go implementation:
package main
import "fmt"
type MaxHeap struct {
data []int
size int
}
func Constructor() *MaxHeap{
return &MaxHeap{}
}
func (t *MaxHeap) sizes() int{
return t.size
}
func (t *MaxHeap) isEmpty() bool{
return t.size==0
}
func (t *MaxHeap) parent(index int) int{
if index==0 {
panic("index 0 dont have parent")
}
return (index-1)/2
}
func (t *MaxHeap) leftChild(index int) int{
return 2*index+1
}
func (t *MaxHeap) rightChild(index int) int{
return 2*index+2
}
func (t *MaxHeap) add(v int) {
t.data=append(t.data,v)
t.size++
newValueIndex := t.size-1
if newValueIndex!=0 {
t.shiftUp(newValueIndex)
}
}
func (t *MaxHeap) shiftUp(index int) {
parent:=t.parent(index)
for parent>=0 && t.data[index]>t.data[parent] {
tmp:=t.data[index]
t.data[index]=t.data[parent]
t.data[parent]=tmp
index=parent
if parent==0 {
break
}
parent= t.parent(index)
}
}
func (t *MaxHeap) extractMax() int{
max:=t.data[0]
t.data[0]=t.data[t.size-1]
t.size--
t.data=t.data[:t.size] //移除最后一個(gè)元素,其實(shí)也可以不用刪吧
t.shiftDown(0)
return max
}
func (t *MaxHeap) shiftDown(index int) {
for t.leftChild(index)<=t.size-1 && t.rightChild(index)<=t.size-1 {
leftIndex:=t.leftChild(index)
rightIndex:=t.rightChild(index)
var bV int
var bI int
if t.data[leftIndex]>t.data[rightIndex] {
bV=t.data[leftIndex]
bI=leftIndex
} else {
bV=t.data[rightIndex]
bI=rightIndex
}
if t.data[index]>bV {
break
}
tmp:=t.data[index]
t.data[index]=bV
t.data[bI]=tmp
index=bI
}
}
func main() {
m:=Constructor()
println(m.sizes())
m.add(1)
m.add(2)
m.add(3)
m.add(4)
m.add(5)
m.add(6)
m.add(7)
m.add(8)
fmt.Println(m.data)
fmt.Println(m.extractMax())
fmt.Println(m.data)
fmt.Println(m.size)
}
Max Heap 最大堆實(shí)現(xiàn)
畫了個(gè)圖檢驗(yàn)了一下這個(gè)簡(jiǎn)單測(cè)試用例
Max Heap 最大堆實(shí)現(xiàn)
參考的老師的圖
Max Heap 最大堆實(shí)現(xiàn)
最小堆
package main
import "fmt"
//minheap只要把maxheap的shiftup shiftdown 箭頭反轉(zhuǎn)一下就可以了 ,把小元素網(wǎng)上浮,大元素往下沉
type MinHeap struct {
data []int
size int
}
func Constructor() *MinHeap{
return &MinHeap{}
}
func (t *MinHeap) sizes() int{
return t.size
}
func (t *MinHeap) isEmpty() bool{
return t.size==0
}
func (t *MinHeap) parent(index int) int{
if index==0 {
panic("index 0 dont have parent")
}
return (index-1)/2
}
func (t *MinHeap) leftChild(index int) int{
return 2*index+1
}
func (t *MinHeap) rightChild(index int) int{
return 2*index+2
}
func (t *MinHeap) add(v int) {
t.data=append(t.data,v)
t.size++
newValueIndex := t.size-1
if newValueIndex!=0 {
t.shiftUp(newValueIndex)
}
}
func (t *MinHeap) shiftUp(index int) {
parent:=t.parent(index)
for parent>=0 && t.data[index]<t.data[parent] {
tmp:=t.data[index]
t.data[index]=t.data[parent]
t.data[parent]=tmp
index=parent
if parent==0 {
break
}
parent= t.parent(index)
}
}
func (t *MinHeap) extractMin() int{
min:=t.data[0]
t.data[0]=t.data[t.size-1]
t.size--
t.data=t.data[:t.size] //移除最后一個(gè)元素,其實(shí)也可以不用刪吧
t.shiftDown(0)
return min
}
func (t *MinHeap) shiftDown(index int) {
for t.leftChild(index)<=t.size-1 && t.rightChild(index)<=t.size-1 {
leftIndex:=t.leftChild(index)
rightIndex:=t.rightChild(index)
var bV int
var bI int
if t.data[leftIndex]<t.data[rightIndex] {
bV=t.data[leftIndex]
bI=leftIndex
} else {
bV=t.data[rightIndex]
bI=rightIndex
}
if t.data[index]<bV {
break
}
tmp:=t.data[index]
t.data[index]=bV
t.data[bI]=tmp
index=bI
}
}
func main() {
m:=Constructor()
m.add(1)
m.add(2)
m.add(3)
m.add(4)
m.add(5)
m.add(6)
m.add(7)
m.add(8)
fmt.Println(m.data)
fmt.Println(m.size)
fmt.Println(m.extractMin())
fmt.Println(m.data)
fmt.Println(m.size)
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
fmt.Println(m.extractMin())
}
優(yōu)先隊(duì)列
優(yōu)先隊(duì)列這里妥妥的就是一個(gè)適配器模式的典例
package main
type PriorityQueue struct {
maxHeap *MaxHeap
}
func (t *PriorityQueue) size() int{
return t.maxHeap.sizes()
}
func (t *PriorityQueue) isEmpty() bool{
return t.maxHeap.isEmpty()
}
func (t *PriorityQueue) front() int{
if t.size()==0 {
panic("queue is empty")
}
return t.maxHeap.data[0]
}
func (t *PriorityQueue) enqueue(v int){
t.maxHeap.add(v)
}
func (t *PriorityQueue) dequeue(){
t.maxHeap.extractMax()
}
