堆和栈及其实现方法

                                         关于堆和栈

- 以前学习程序设计的时候都是将堆栈合起来一起说的，后来经过很久以后的学才发现堆栈完全是两个东西，也不知道为什么要将堆栈合起来一起说，栈很好理解，就是一个先进后出表，但是堆是一种数据结构。感觉栈和队列可以合起来说，但是堆明显是不能和堆合起来说的。

---

首先是栈，栈很好理解，就和它的名字一样先进后出表，先进栈的元素会相对后面出栈，如图所示

在代码实现方面可以使用数组来模拟，但是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("\n");

    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）的复杂度之内完成。所以在平时不会手写堆，一般都用优先队列来实现。