堆优先队列

# 堆

堆分为大顶堆（大根堆）和小顶堆（小根堆）两种。对于一个堆首先是一颗完全二叉树即只有最后一层不为空且最后一层从左往右是连续的不为空。其次如果是大顶堆，根元素是最大值，子节点比父节点都要小，小顶堆则相反

# 1. 上浮

每次插入元素时，都往堆最后一个的地方插入元素，为了维护堆的性质则需对插入的元素进行上浮操作。如果是大顶堆的话，插入的元素如果比父节点大就要与父节点交换值。

//大顶堆
function up (index){
    let father = Math.floor((index-1)/2) //获取父节点的下标
    // 如果是大顶堆的话，当父节点的值小于当前节点的值时就要交换节点。二叉树用数组arr储存。
    while(father>=0&&arr[father]<arr[index]){
    	[arr[index],arr[father]] = [arr[father],arr[index]] //交换子节点的值和父节点的值。
        index = father 
        father = Math.floor((index-1)/2)
    } 
}

# 2. 下沉

当根节点弹出的时候，则需要将最后一个元素放在根节点中，为了维护堆的性质则需要对根节点进行下沉操作。如果是大顶堆的话，插入的元素如果比父节点大就要与父节点交换值。

//大顶堆
function down(index){ 
	if(!arr[index*2+1]) return //如果不存在左子树的话就不下沉了
	//如果右子树不存在的话就选左子树否则比较左子树以及右子树的大小谁大选谁
	let son = arr[index*2+2]?arr[index*2+1]>arr[index*2+2]?index*2+1:index*2+1:index*2+1 
	while(son<arr.length&&arr[index]<arr[son]){
		[arr[index],arr[son]] = [arr[son],arr[index]]
		index = son
		son = arr[index*2+2]?arr[index*2+1]>arr[index*2+2]?index*2+1:index*2+1:index*2+1 
	}
}

# 3. 插入元素

每次往堆插入元素时在最后的地方插入并进行上浮的操作。

function push (val){
	arr.push(val)
	up(arr.length-1)
}

# 4. 弹出元素

每次从堆中弹出根元素然后将最后一个元素放在根元素上进行下浮操作。

function pop (){
	let val = arr[0]
	arr[0] = arr.pop()
	down(0)
	return val
}

# 5. 创建一个堆类

class Quque{
    constructor(quque=[],compare=(a,b)=>a-b){
        this.compare = (a,b)=>compare(this.arr[a],this.arr[b]) //比较函数如果没传的话默认构建大顶堆
        this.quque = quque //用于一开始接受一个数组然后用build将这个数组构建成堆
        this.arr = []
    }
    // 如果一开始传入了一个数组就将其构建成一个堆
    build(){ 
        this.quque.forEach((a)=>this.push(a))
        this.quque = []
    }
    up(index){
        let father = Math.floor((index-1)/2)
        while(father>=0&&this.compare(index,father)>0){
            [this.arr[father],this.arr[index]] = [this.arr[index],this.arr[father]]
            index = father
            father = Math.floor((index-1)/2)
        }
    }
    down(index){
        let son = this.arr[index*2+2]?this.arr[index*2+1]<this.arr[index*2+2]?index*2+2:index*2+1:index*2+1
        while(this.compare(index,son)<0){
            [this.arr[index],this.arr[son]] = [this.arr[son],this.arr[index]]
            index = son
            son = this.arr[index*2+2]?this.arr[index*2+1]<this.arr[index*2+2]?index*2+2:index*2+1:index*2+1
        }
    }
    push(val){
        this.arr.push(val)
        this.up(this.arr.length-1) 
    }
    pop(){
        let val = this.arr[0]
        this.arr[0] = this.arr.pop()
        this.down(0)
        return val
    }
}

# 优先队列

优先队列顾名思义就是一个队列，队列里面的元素有优先级比如每次弹出的都是最大值或者最小值。优先队列可以用堆进行实现。

# 1.前 k 个高频元素

因为要获取前 k 个高频元素，所以这里使用小顶堆。当堆的元素的个数超过了 k 就将最小元素即根元素弹出，因此当遍历一遍后就留下了最大的 k 个元素。

class root {
    constructor(){
        this.arr = []
    }
    up(index){
        let fatherIndex = Math.floor((index-1)/2)
        while(fatherIndex>=0&&this.arr[index][1]<this.arr[fatherIndex][1]){
            [this.arr[index],this.arr[fatherIndex]] = [this.arr[fatherIndex],this.arr[index]]
            index = fatherIndex
            fatherIndex = Math.floor((index-1)/2)
        }
    }
    down(index){
        if(!this.arr[index*2+1]) return
        let sonindex = this.arr[index*2+2]?this.arr[index*2+1][1]>this.arr[index*2+2][1]?index*2+2:index*2+1:this.arr[index*2+1][1] 
        while(sonindex<this.arr.length&&this.arr[index][1]>this.arr[sonindex][1]){
            [this.arr[index],this.arr[sonindex]] = [this.arr[sonindex],this.arr[index]]
            index = sonindex
            if(!this.arr[index*2+1]) return
            sonindex = this.arr[index*2+2]?this.arr[index*2+1][1]>this.arr[index*2+2][1]?		index*2+2:index*2+1:this.arr[index*2+1][1]         
        }
    }
    push(list){
        this.arr.push(list)
        this.up(this.arr.length-1)
    }
    pop(){
        this.arr[0] = this.arr.pop()
        this.down(0)
    }
    size(){
        return this.arr.length
    }
}

var topKFrequent = function(nums, k) {
    let map = new Map()
    let quque = new root()
    for(let num of nums){
        map.set(num,(map.get(num)||0)+1)
    }
    for(let array of map.entries()){
        quque.push(array)
        if(quque.size()>k){
            quque.pop()
        }
    }
    return quque.arr.map((a)=>a[0])
};

# 2. 将数组和减半的最少操作次数

将数组放进大顶堆中，每次将根元素减半，减半后看看根元素是否比子元素小，如果小的话就下沉直到数组和小于数组的一半。

class Quque{
    constructor(quque=[],compare=(a,b)=>a-b){
        this.compare = (a,b)=>compare(this.arr[a],this.arr[b])
        this.quque = quque
        this.arr = []
    }
    build(){
        this.quque.forEach((a)=>this.push(a))
        this.quque = []
    }
    up(index){
        let father = Math.floor((index-1)/2)
        while(father>=0&&this.compare(index,father)>0){
            [this.arr[father],this.arr[index]] = [this.arr[index],this.arr[father]]
            index = father
            father = Math.floor((index-1)/2)
        }
    }
    down(index){
        let sonindex = this.arr[index*2+2]?this.arr[index*2+1]<this.arr[index*2+2]?index*2+2:index*2+1:index*2+1
        while(this.compare(index,sonindex)<0){
            [this.arr[index],this.arr[sonindex]] = [this.arr[sonindex],this.arr[index]]
            index = sonindex
            sonindex = this.arr[index*2+2]?this.arr[index*2+1]<this.arr[index*2+2]?index*2+2:index*2+1:index*2+1
        }
    }
    push(val){
        this.arr.push(val)
        this.up(this.arr.length-1) 
    }
    pop(){
        let val = this.arr[0]/2
        this.arr[0] = val
        this.down(0)
        return val
    }
}

var halveArray = function(nums) {
    let sum = 0,quque = new Quque(nums),res =0
    quque.build()
    nums.forEach((a)=>{
        sum+=a   
    })
    let target = sum/2
    while(sum>target){
        let value = quque.pop()
        sum -= value
        res++
    }
    return res

};

算法堆优先队列

# 堆