一：什么是堆

堆结构-->数组对象
可以视为一棵完全二叉树

$\green{树中每个节点中存放该节点中值的那个元素相对应}$
a[i]-->下标$i$是节点编号，a[i]是该节点编号对应的值

二：堆的性质

$1.\blue{大根堆}$^[1]

除根结点外每个节点$i$，a[父亲(i)]>=a[i]
即 除根结点外，所有节点的值都不超过其父节点值
堆中最大的元素存在根节点中

$2.\purple{小根堆}$^[2]

除根结点外每个节点$i$，a[父亲(i)]<a[i]
即 除根结点外，所有节点的值都不小于其父节点值
堆中最小的元素存在根节点中
（代码以小根堆为例）

三：put

put操作：在堆中<加入>一个元素

1.在堆尾加入一个元素，并把节点设为设为<当前结点>

void put(int d){
	int son,pa;
	//新增一个节点，值为d 
	heap[++heap_size]=d;
	son=heap_size;
	while(son>1){//向上取整 
		//找到父节点 
		pa=son>>1;
		//如果父节点的值小于等于儿子节点，调整完毕 
		if(heap[son]>=heap[pa]) break;
		//向上取整 
		swap(heap[son],heap[pa]);
		son=pa;
	}
} 

四：get

get：<返回>堆顶的值，并删除堆顶

int get(){
	int res=heap[1];
	heap[1]=heap[heap_size--];
	int pa=1,son;
	while(2*pa<=heap_size){
		son=2*pa;
		if(son+1<=heap_size&&heap[son+1]<heap[son]) son++;
		if(heap[pa]<=heap[son]) break;
		swap(heap[pa],heap[son]);
		pa=son;
	}
	return res;
}

---

1. 大根堆
   ↩︎

2. 小根堆
   ↩︎