二叉堆

二叉堆是一种支持插入、删除、查询最值得数据结构。它其实是一颗满足“堆”性质的完全二叉树，树上的每个节点均带有一个权值。

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

• 我们以大根堆举例
  • Insert
    • 向二叉堆中将带有权值val的点直接放在储存二叉堆的数组末尾，即放入在完全二叉树中的最后一个节点，然后通过交换的方式向上调整，直至满足堆的性质。时间复杂度为堆的深度O(logn)

    • int heap[SIZE],n;
      void up(int p){
      	while(p>1){
      		if(heap[p]>heap[p/2]){
      			swap(heap[p],heap[p/2]);
      			p/=2;
      		}else break;
      	}
      }
      void Insert(int val){
      	heap[++n]=val;
      	up(n);
      }

  • GetTop
    • 返回堆顶值，即最大值

    • int GetTop(){
      	return heap[1];
      }

  • Extract
    • 把堆顶从二叉堆中删除（为什么不删除数组最后一位呢？因为最后一位并不存在最大最小的性质）。
    • 我们把堆顶heap[1]与储存在数组末尾的节点heap[n]交换，然后n–（即移除数组末尾节点），然后通过交换将此时的堆顶向下调整。

    • void down(int p){
      	int s=p*2;//左子节点get 
      	while(s<=n){
      		if(s<n&&heap[s]<heap[s+1])s++;//取左右子节点中较大者 
      		if(heap[s]>heap[p]){//子节点大于父节点 
      			swap(heap[s],heap[p]);
      			p=s,s=p*2;
      		}
      		else break;
      	}
      }
      void Extract(){
      	head[n--]=heap[1];
      	down(1);
      }
  • Remove
    • 把纯在在数组下标p位置的节点从二叉堆中删除。
    • 先交换heap[p]与heap[n]，再将heap[p]向上，向下调整。

    • void Remove(int p){
      	heap[n--]=heap[p];
      	up(p),down(p); 
      }

• C++提供了priority_queue实现大根堆与小根堆，但是不支持Remove操作（虽然我不知道这个操作的具体用途哈哈哈）
• 实际上堆就是依靠交换，向上，向下来满足性质，我们选择借用数组末尾元素进行操作的原因是该节点的存在与否不影响树中的其他节点。