（2.19）数据结构

堆

性质：儿子的值一定不小于父亲的值，树的结构是从上到下，从左到右紧凑排列的。

插入数值：先在末尾插入该数值，然后不断向上提升直到没有大小颠倒为止。

删除最小值：首先把堆的最后一个节点的数值复制到根节点上，并且删除最后一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中，如果有2个儿子，那么选择数值较小的儿子（如果儿子比自己小的话）进行交换。

时间复杂度：堆的两种操作所花的时间与树的深度成正比，n个元素的时间复杂度是O(logn)

堆的实现：
给每个节点赋予一个编号，用数组来存储
左儿子的编号是自己的编号x2 + 1
右儿子的编号是自己的编号x2 + 2

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int MAX_N = 1000;
int heap[MAX_N];
int sz = 0; 

void push(int x){
	// 自己节点的编号
	int i = sz ++;
	
	while(i > 0){
		// p是父亲节点的编号
		int p = (i - 1) / 2;
		
		// 如果已经没有大小颠倒则退出循环
		if(heap[p] <= x)
			break;
		
		//把父亲节点的数值放到儿子节点位置上，并存储父亲节点索引
		heap[i] = heap[p];
		i = p; 
	}
	heap[i] = x; 
}

int pop(){
	// 最小值
	int ret = heap[0];
	
	//x 为要放到根节点的数值
	int x = heap[--sz];
	
	// 从根开始向下交换
	int i = 0;
	while(i*2 + 1 < sz){
		// 比较两个儿子的值
		int a = i*2 + 1;
		int b = i*2 + 2;
		if(b < sz && heap[b] < heap[a])
			a = b;
		
		// 如果已经没有大小颠倒则退出
		if(heap[a] >= x)
			break;
		
		//把儿子的数值提上来
		heap[i] = heap[a];
		i = a;
	} 
	heap[i] = x;
	return ret;
}
void printheap(){
	for(int i = 0 ; i < sz ; i ++)
		printf("%d ", heap[i]);
	printf("\n");
}
void solve(){
	push(1);
	printheap(); 
	push(2);
	printheap();
	push(4);
	printheap();
	push(7);
	printheap();
	push(8);
	printheap();
	push(5);
	printheap();
	int a = pop(); // 1
	printheap();					 
} 	


int main(){	
	solve(); 
	return 0;
}

优先队列（STL）

优先输出最大的元素

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
void solve(){
	priority_queue<int> pque;
	
	pque.push(3);
	pque.push(5);
	pque.push(1);
	
	while(!pque.empty()){
		// 获取并删除最大值
		cout << pque.top() << endl;  // 5 3 1
		pque.pop(); 
	}	 
} 	


int main(){	
	solve(); 
	return 0;
}

优先输出最小的元素

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
void solve(){
	priority_queue<int, vector<int>, greater<int> > pque;
	
	pque.push(3);
	pque.push(5);
	pque.push(1);
	
	while(!pque.empty()){
		// 获取并删除最小值
		cout << pque.top() << endl; // 1 3 5
		pque.pop(); 
	}	 
} 	


int main(){	
	solve(); 
	return 0;
}