关于堆和栈
- 以前学习程序设计的时候都是将堆栈合起来一起说的，后来经过很久以后的学才发现堆栈完全是两个东西，也不知道为什么要将堆栈合起来一起说，栈很好理解，就是一个先进后出表，但是堆是一种数据结构。感觉栈和队列可以合起来说，但是堆明显是不能和堆合起来说的。
首先是栈，栈很好理解，就和它的名字一样先进后出表，先进栈的元素会相对后面出栈，如图所示
在代码实现方面可以使用数组来模拟，但是c++里面有自带的库函数很好用，用法也很简单，在这里展示一下用法就好了。
//头文件
#include <stack>
#include <stdio.h>
using namespace std;
int main() {
//定义,数据元素可以是整形，浮点型，字符型，自定义类型都可以，这里就以整形为例
stack <int> st;
//向栈中放入元素
st.push(1);
st.push(2);
//从栈中取出元素，只能按照顺序取出，每次取栈顶的元素
int temp = st.top();
//从栈顶删除元素，每次也只能删除栈顶元素
st.pop();
//获得栈的大小
int Size = st.size();
//可以打表看一下栈的放入和取出顺序
stack <int> st2;
for(int i=1;i<=10;i++) {
st2.push(i);
printf("%d ",i);
}
printf("
");
while(st2.size()){
printf("%d ",st2.top());
st2.pop();
}
}然后是堆，堆就要比栈复杂一些，堆是一种二叉树，它最重要的性质就是儿子节点的值一定比父亲节点的值更大，除此之外，树的节点是按从上到下，从左到右的顺序紧凑排列的。如图所示就是堆的结构（图片上有儿子大父亲小的，也有相反的，在这里以儿子大父亲小为例说明）
堆的操作一般就插入和删除两个。
堆的插入比较简单，就是将要插入的数据放在末尾，然后不断的向上提升，直到不能提升为止。在这里不用指针来实现，用数组，儿子编号满足
- 左儿子编号是自己编号×2+1
- 右儿子编号是自己编号×2+2
具体操作如图所示
实现插入的操作
int head[MAX_N],sz = 0;
void push(int x) {
//自己节点的编号
int i = sz++;
while(i > 0) {
//父亲节点的编号
int p = (i-1)/2;
//如果已经没有大小颠倒就退出
if(head[p] <= x)
break;
//把父亲节点放下来自己提上去
head[i] = head[p];
i = p;
}
head[i] = x;
}堆删除最小值的时候，首先把堆的最后一个节点的数值复制到根节点上，并且删除最后一个节点，然后不断交换，直到没有大小颠倒为止。在向下交换中，如果有两个儿子节点，那么选择数值较小（如果儿子节点比自己小的话）的儿子节点进行交换。
实现方法如图所示
代码实现
int head[MAX_N],sz = 0;
int pop() {
//最小值
int ret = head[0];
//要提到根的数值
int x = head[--sz];
//从根开始往下交换
int i = 0;
while(i*2 + 1 < sz) {
int a = i*2 + 1;
int b = i*2 + 2;
//比较儿子的值
if(b < sz && head[a] > head[b]) a = b;
//没有大小交换就退出
if(head[a] > x) break;
//把儿子的值提上来
head[i] = head[a];
i = a;
}
head[i] = x;
return ret;
}其实优先队列的实现就是用的堆。每次关于堆的操作（插入，删除）都能够在O（logn）的复杂度之内完成。所以在平时不会手写堆，一般都用优先队列来实现。