Swift 实现二叉堆 —— 创建，增加节点，摘除最大节点

二叉堆其实也就是完全二叉树或者近似完全的二叉树，百科里面讲的是一般用数组来存储，完全二叉树嘛，子节点都是平均分的，不存在一枝特别突兀，这样就可以用数组了，比如父节点是n那子节点就是n/2和n/2+1，所以对给定一个数组，把里面的数字添加到二叉堆里还是稍微的有些容易
直接上代码

import UIKit

var str = "二叉堆"

var a = [96,79,8,7,67,16,57,80,89,25,84,29,78]

//a = [1,23,4,12,3,90]

//幂运算，在playground里pow老是出错，自己写了一个
func poww(_ a:Int,_ b:Int)->(Int)
{
    var temp = 1
    for _ in 0..<b
    {
        temp = temp * a
    }
    return temp
}
//二叉堆的高度，也就是不断地去除以2，看能除几次
func gaodu(_ arr:Array<Int>)->(Int)
{
    var i = arr.count-1
    var j = 0
    while i > 1 {
        i = i/2
        j+=1
    }
    return j+1

}
//这个我还是在原数组上修改，判定子节点的数如果比父节点的数大，那就换一下，因为都是int,n/2 = (n+1)/2，所以左右节点不用考虑了，就酱
func erchadui(){
//二叉堆应该是从一开始，0的位置我上了最大值
 a.insert(Int.max,at: 0)
    for var i in 2..<a.count
    {
        var j = i
        while a[j]>a[j/2]{
            var temp = a[j]
            a[j] = a[j/2]
            a[j/2] = temp
            j=j/2
        }
    }
}

erchadui()
print(a)
//我想着按着树的格式来写吧，就酱
func shuchu(){
    for i in 0..<gaodu(a)
    {
 let leftindex:Int = poww(2,i)
 var rightindex: Int = poww(2,i+1) - 1
        if rightindex > a.count-1
        {
            rightindex = a.count-1
        }
        print(a[leftindex...rightindex])
    }
}


//增加，加在最后面，然后一步一步往上爬就行
func adddui(_ addindex:Int){
    a.append(addindex)
    var j = a.count-1
    while a[j]>a[j/2]{
        var temp = a[j]
        a[j] = a[j/2]
        a[j/2] = temp
        j=j/2
    }

}

//摘除最大的节点，把最小的节点补上去，然后再排序。方法是找子节点那个相对大的，如果父节点小于这个较为大的节点，那就换下位置，直到底
func zhaichuzuida()
{
    if(a.count>1){
        a[1] = a[a.count-1]
 a.remove(at: a.count-1)
        var j = 1;

        while j*2+1 < a.count {
            if(a[j*2]>a[j*2+1])
            {
                if a[j]<a[j*2]
                {
                    var temp = a[j]
                    a[j] = a[j*2]
                    a[j*2] = temp
                }

            }else
            {
                if a[j]<a[j*2+1]
                {
                    var temp = a[j]
                    a[j] = a[j*2+1]
                    a[j*2+1] = temp
                }
            }
            j*=2
        }
    }
}

//adddui(77)
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
//zhaichuzuida()
shuchu()

//结果就这样
[96]
[89,78]
[80,16]
[7,29]

安利，看着它的动画寻思的