MaxHeap 最大堆 MinHeap 最小堆 PriorityQueue 优先队列实现
454 / 0 / 创建于 4年前 /
twisted-fate 的个人博客
复盘:
优化了shiftDown的判断减少了重复代码 , 在遍历中做部分边界条件终止
shiftDown 边界定义出错 , 正确的应该是该元素没有左右child后终止
shiftUp的代码也可以优化一些减少代码重复判断 , 而且边界条件其实也没定义好
pesudo code :
// 0 1 2 3 4 5
[2,9,8,5,1,7] 从0开始 , 某个节点的parent=(i-1)/2 , leftP=2i+1 rightP=2i+2
MaxHeap {
data []int
size int initial 0 //没有c++的那些helper function , 额外添加一个变量存储size
}
size() {
return t.size
}
isEmpty() {
return data.size==0
}
getParentIndex(index) {
if index==0 //root节点没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 { // 优化,小于的时候就停止了,不需要一直遍历到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) {
//优化了一遍,去除了重复代码
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] //移除最后一个元素,其实也可以不用删吧
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)
}
画了个图检验了一下这个简单测试用例
参考的老师的图
最小堆
package main
import "fmt"
//minheap只要把maxheap的shiftup shiftdown 箭头反转一下就可以了 ,把小元素网上浮,大元素往下沉
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] //移除最后一个元素,其实也可以不用删吧
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())
}
优先队列
优先队列这里妥妥的就是一个适配器模式的典例
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()
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号